Переговоры продолжались черепашьими темпами, но не прекращались. Хотя переговоры по соглашению об окончательном статусе не начались в срок, установленный в 1996 году, наметились положительные сдвиги. После интенсивных посреднических усилий американской администрации и долгих и трудных переговоров в октябре 1998 года в Уай Плантейшн было подписано соглашение о передислокации ЦАХАЛа на Западном берегу, согласно которому ПА были переданы дополнительные 13 % территории Западного берега. Американские наблюдатели предположили, что между Арафатом и Нетаньяху существовало молчаливое понимание, согласно которому Нетаньяху передал палестинцам сравнительно небольшие территории в обмен на мир и спокойствие. Исаак Молчо, главный переговорщик Нетаньяху, сравнил эту политику с проглатыванием лягушек: вы можете проглотить десять маленьких лягушек, но не одну большую.
Нетаньяху имел серьезные проблемы с доверием. Он дал обещания, которые не смог сдержать, как умеренным, так и радикалам в своем правительстве. Правые требовали от него аннулировать соглашения Осло, чего он был сделать не в состоянии. Они рассматривали соглашение в Уай Плантейшн как нарушение обещания. Из-за своей политической привязанности он пообещал своим умеренным партнерам прогресс в политических шагах, способствующих мирному процессу, и они были разочарованы, потому что ни один из них не осуществился. Likud начала распадаться изнутри, а присоединившиеся было к ней ранее отколовшиеся партии теперь покинули ее, уменьшив поддержку в Кнессете. Пытаясь предотвратить падение своего правительства, Нетаньяху призвал к вотуму доверия. Поражение означало бы новые выборы, а нынешние члены Кнессета обычно против них. Но на этот раз правые выбили почву из-под ног Нетаньяху. Кнессет проголосовал против него, правительство пало, и Нетаньяху был вынужден провести общенациональные выборы.
На выборах премьер-министра в мае 1999 года подавляющим большинством голосов победил Эхуд Барак, лидер партии Yisrael Ahat («Единый Израиль») – союза HaAvoda с другими небольшими партиями. Избирательная система Израиля была изменена после 1996 года, и теперь электорат голосовал напрямую за премьер-министра. Была надежда, что эта система, больше похожая на систему президентских выборов в США, создаст более стабильные правительства. Но на самом деле это привело к еще большему раздроблению. На выборах в Кнессет основные партии получили меньшее количество мест, что было выгодно малым и средним партиям. Yisrael Ahat получила 26 мест, Likud – 19, Shas – 17 и Meretz – десять, а оставшиеся места были разделены между многочисленными небольшими партиями, каждая из которых получила от двух до шести мест. Наряду с прямым голосованием за премьер-министра была сохранена старая парламентская система, что позволило избирателям разделить свои голоса, отдав один голос за премьер-министра, а другой – за партию по своему выбору. Ожидание, что прямые выборы премьер-министра нейтрализуют необходимость коалиционного торга, оказалось трагическим просчетом. Прямые выборы премьер-министра вскоре были отменены, и восстановлена прежняя система избрания по партийным спискам. Однако возврат к старой системе больше не привел к двухпартийной системе, заправлявшей израильской политикой в 1980-х годах.
На массовом митинге после победы сторонники Барака скандировали: «Только не Shas». Эту партию отождествляли с общественными деятелями, которым было предъявлено обвинение в коррупции. У нее был имидж партии, заинтересованной исключительно в благополучии своих избирателей, и она была политически ненадежной. Но у Барака не было выбора. Ему пришлось иметь дело с Shas, а также убедить левую Meretz, которая обещала своим избирателям не вступать в коалицию с Shas, присоединиться к коалиции на основе возобновленных мирных переговоров. В коалицию также вошли Партия центра (новая партия, образованная умеренными бывшими лидерами Likud и видными политическими деятелями), ультраортодоксальные Yahadut Hatorah (иудаизм Торы) и Yisrael Baʻaliya (игра слов «Израиль» и «алия»), партия выходцев из бывшего Советского Союза. Это была непрочная коалиция. В сентябре 1999 года Yahadut Hatorah вышла из нее в знак протеста против несоблюдения субботы, а в июне 2000 года Meretz вышла из-за спора с Shas, хотя продолжала поддерживать правительство ради мирного процесса. Когда Барак уехал на саммит в Кэмп-Дэвиде в июле 2000 года (о чем будет сказано позже), Shas и Yisrael Baʻaliya также покинули коалицию. Затем партия Центра стала рассыпаться. Таким образом, несмотря на впечатляющую победу на выборах, у Барака не осталось реальной политической поддержки.