Des négociations secrètes conduites en Norvège débouchent en 1993 sur une reconnaissance mutuelle. L’OLP reconnaît le droit d’Israël à exister en paix et en sécurité. Israël reconnaît l’OLP comme représentante du peuple palestinien. Le 13 septembre 1993, Yitzhak Rabin et Yasser Arafat signent à Washington une Déclaration de principes sous l’égide de Bill Clinton. Le projet repose sur une logique progressive. Une Autorité palestinienne doit exercer une autonomie croissante dans certaines parties de Gaza et de Cisjordanie pendant une période intérimaire. Les questions les plus difficiles doivent être réglées ensuite : frontières, Jérusalem, réfugiés, colonies, sécurité et souveraineté. Oslo II, signé en 1995, répartit la Cisjordanie en zones A, B et C dotées de niveaux de contrôle différents. Cette progressivité devait créer progressivement de la confiance. Elle produit cependant un risque majeur : ce qui devait être provisoire devient durable.
Aucun mécanisme suffisamment contraignant ne garantit l’achèvement du processus. L’asymétrie entre Israël, État souverain, et l’Autorité palestinienne reste importante. Des adversaires du compromis existent en outre dans les deux sociétés. Rabin est assassiné le 4 novembre 1995 par un extrémiste israélien opposé au processus. Le Hamas mène des attentats contre des civils israéliens. La poursuite de la colonisation contribue parallèlement à modifier les réalités territoriales. Oslo constitue donc un paradoxe : jamais les deux mouvements nationaux n’avaient été aussi proches d’une reconnaissance réciproque institutionnalisée, mais les accords créent un processus de paix sans définir immédiatement la paix finale.