המתח בישראל אשר נבע מהמשך פעילות הטרור והכעס בקרב חלקים גדולים מהציבור הישראלי על הוויתורים הטריטוריאליים, הוביל לרצח ראש הממשלה יצחק רבין ב-4 בנובמבר 1995 על ידי יגאל עמיר, סטודנט יהודי בעל אוריינטציה ימנית קיצונית. בעקבות רצח רבין, שמעון פרס מילא את מקום ראש ממשלת ישראל. פרס המשיך במדיניות רבין בתמיכה בתהליך אוסלו.
במהלך 1996, זכה ארגון הפתח, הארגון הגדול באש"ף, לרוב במועצה המחוקקת הפלסטינית ויאסר ערפאת הפך ליו"ר הרשות הפלסטינית. עם הקמת הרשות הפלסטינית, היא הפכה למוקד הפוליטי הפלסטיני, והיוותה את הזירה העיקרית לריבונות הפלסטינית המתהווה. במהלך השנים בין הסכמי אוסלו לבין פרוץ האינתיפאדה השנייה, נדחק אש"ף לשוליים הבינלאומיים תוך שהרשות הפלסטינית תופסת במידה רבה את מקומו. הזהות שנוצרה בין שני הגופים מכך שראש אש"ף עמד בראש הרשות ושצמרת הרשות הורכבה מצמרת הפת"ח הקלה על המעבר. עם זאת אש"ף נותר הארגון היציג של הפלסטינים והשיחות נערכו עמו ולא עם הרשות הפלסטינית.
בתחילת 1996 התנקש שירות הביטחון הכללי הישראלי בחייו של יחיא עיאש באמצעות טלפון סלולרי ממולכד. בתגובה ביצע ארגון החמאס גל פיגועי התאבדות בישראל. בעקבות פיגועים אלה החלה הרשות הפלסטינית לפעול נגד חמאס ולדכא את פעילותה.
במהלך שנת 1996, בעקבות הספקות שהחלו להתעצם בקרב חלקים גדולים מהציבור הישראלי לגבי תהליך אוסלו, במערכת הבחירות שנערכה באותה השנה עלה לשלטון בנימין נתניהו על רקע הבטחותיו לנקוט בקו נוקשה יותר במשא ומתן עם הרשות הפלסטינית והתניית כל התקדמות מדינית בפעולות אותן תנקוט הרשות למניעת פעילות הטרור נגד ישראלים. במהלך כהונתו, על אף שנתניהו לא ביטל את תהליך אוסלו, לדבריו הוויתורים שעשו הישראלים עודדו את הפלגים הפלסטינים הקיצוניים, מבלי שישראל קיבלה כל מחוות ממשיות בתמורה מצד הפלסטינים. בשל כך, נתניהו הביע אי ההסכמה עם הנחת היסוד המרכזית של תהליך אוסלו, שתהליך המשא ומתן עם הפלסטינים צריך להמשיך להתבצע בשלבים והדגיש כי קיום הנסיגות של ישראל צריכים להתבצע רק במקביל לקיום ההתחייבויות של הרשות הפלסטינית וכי המשך הוויתורים הישראלים צריך להגיע רק לאחר שיושגו הסכמים משותפים בין הצדדים לגבי סוגיות הליבה בסכסוך הישראלי-פלסטיני, כמו מעמדה של ירושלים ושינוי האמנה הלאומית הפלסטינית. מנגד, התומכים בתהליך אוסלו טענו שתהליך המשא ומתן בשלבים יוביל להכרה הדדית ולדו-קיום של הפלסטינים עם ישראל אשר יוביל בהמשך לפיוס אמיתי בין הפלסטינים לישראל, כאשר המשא ומתן על סוגיות הליבה של הסכסוך יתבצע בשלבים המאוחרים יותר של תהליך המשא ומתן.
בינואר 1997 חתם נתניהו על הסכם חברון עם הרשות הפלסטינית אשר בעקבותו צה"ל העביר חלקים בחברון לשליטה פלסטינית מלאה בעוד שהאזור בחברון בו התרכז היישוב היהודי בחברון אשר הכיל גם 40 אלף תושבים פלסטינים, נשאר בשליטת של צה"ל. במהלך שנת זו, בעקבות שני פיגועי התאבדות קטלניים בירושלים אשר הוצאו לפועל על ידי ארגון החמאס, נשלחו שני סוכנים חשאיים ישראלים לירדן לחסל את ראש הלשכה המדינית של ארגון החמאס, ח'אלד משעל, באמצעות רעל מיוחד (ראו ניסיון ההתנקשות בח'אלד משעל). עם זאת, הפעולה הסתבכה והסוכנים נתפסו על ידי הירדנים. בתמורה לשחרורם של הסוכנים שלחה ישראל תרופת נגד אשר הצילה את חייו של משעל, ובמקביל שחררה עשרות אסירים ביטחוניים פלסטינים ובראשם השייח' אחמד יאסין. שחררו של יאסין והקמת כוחות הביטחון של הרשות הפלסטינית הביאו להפוגה זמנית של פיגועי התאבדות עד לפרוץ האינתיפאדה השנייה.
בסופו של דבר, חוסר התקדמות בתהליך השלום הביא לתהליך משא ומתן אינטנסיבי שנערך במשך עשרה ימים במקום מבודד בארצות הברית ובמעורבותה המלאה של ארצות הברית ודיפלומטים נוספים שנשלחו על ידי המלך חוסיין. תהליך המשא ומתן הוביל להסכם ואי בין ישראל לרשות הפלסטינית, אשר היווה תוספת להסכמי אוסלו שקדמו לו, ופירט את הצעדים אותם ממשלת ישראל והרשות הפלסטינית צריכים לנקוט על מנת ליישם את הסכם הביניים משנת 1995 (הסכם אוסלו ב') וקבע לוח זמנים מדויק לביצוע הצעדים הנדרשים תוך שמירה על הדדיות. ההסכם נחתם ב-23 באוקטובר 1998, בטקס רשמי בבית הלבן, על ידי ראש ממשלת ישראל בנימין נתניהו ויו"ר הרשות הפלסטינית יאסר ערפאת. חתימת הסכם ואי על ידי בנימין נתניהו היוותה את אחד הגורמים לנפילת ממשלתו של נתניהו. כמו כן, מימוש ההסכם נתקל בהמשך בקשיים משני הצדדים ולא כובד במלואו.
בשנת 1999, נבחר אהוד ברק לראשות הממשלה. ברק המשיך במדיניות רבין בתמיכה בתהליך אוסלו. ב-24 במאי 2000, 18 שנים לאחר שישראל השתלטה על אזור דרום לבנון במהלך מלחמת לבנון הראשונה, כוחות צה"ל נסוגו באופן חד צדדי ומוחלט מרצועת הביטחון בדרום לבנון. בהמשך תקופת כהונתו של אהוד ברק ניסה ברק לכפר על הקיפאון במשא ומתן עם הפלסטינים ובמטרה לשים קץ למעגל האלימות ההולך וגובר עם הפלסטינים, דחף ברק לפסגה בתיווך נשיא ארצות הברית, ביל קלינטון, שבה יושג הסדר קבע והסכסוך יחתם אחת ולתמיד. בעקבות מהלך זה, התפרקה רוב ממשלתו של ברק והוא נסע ביולי 2000 לקמפ דייוויד כמעט ללא תמיכה בכנסת. בקמפ דייוויד התקיים משא ומתן מרתוני בין ראש ממשלת ישראל, אהוד ברק ליושב ראש הרשות הפלסטינית יאסר ערפאת, בחסות נשיא ארצות הברית ביל קלינטון. המשא ומתן הגיע לבסוף למבוי סתום לאחר שערפאת לא קיבל את ההצעה אשר הוצגה בפניו אשר נוסחה על ידי המתווכים הישראלים והאמריקנים. ברק הטיל לאחר מכן את האשמה על יאסר ערפאת בסירוב לבצע כל ויתור או להעלות הצעה נגדית להצעות שהעלו ברק וקלינטון - טענה שזכתה לגיבויו של הנשיא קלינטון והנסיך הסעודי בנדר.
2000 – 2005: האינתיפאדה השנייה.
ב-28 בספטמבר 2000 פרצה האינתיפאדה השנייה כמענה לתביעתו של ראש הממשלה אהוד ברק להכריז על קץ הסכסוך, כאשר התואנה הייתה שעלייתו של אריאל שרון להר הבית איימה על קודשי האסלאם. במסגרת האינתיפאדה השנייה, ישראל והפלסטינים מצויים במאבק מזוין אשר נמשך עד היום עם ארגוני הטרור הפלסטינים. האינתיפאדה השנייה מנתה עד היום אלפי הרוגים בשני הצדדים, הן בקרב הלוחמים והן בקרב אזרחים והפכה קטלנית יותר מאשר האינתיפאדה הראשונה. חלק גדול מהציבור הפלסטיני החשיב את האינתיפאדה השנייה כמלחמת שחרור לאומית לגיטימית נגד כובש זר.
כישלון תהליך אוסלו, פרוץ האינתיפאדה השנייה והעלייה בכמות פיגועי הטרור הפלסטיניים הובילה את מרבית הציבור הישראלי וההנהגה הפוליטית בישראל לאבד את האמון ברשות הפלסטינית כשותפה אמיתית לשלום. עקב העלייה בכמות פיגועי הטרור במהלך האינתיפאדה השנייה, אשר בוצעו בעיקר על ידי ארגון החמאס נגד אזרחים ישראלים, החלו כוחות צה"ל לבצע פשיטות ומעצרים באופן שוטף באזור הגדה המערבית. בנוסף, ישראל הגבירה את מדיניות החיסולים (ראו סיכול ממוקד) של פעילי החמאס. בתחילה מדיניות זו הופעלה כנגד פעילים צבאיים שנחשבו כ"פצצות מתקתקות", אך ככל שעבר הזמן הופעלה מדיניות זו גם כנגד אנשי "הזרוע הפוליטית" של הארגון, המפיחים רוח במפרשי "הזרוע הצבאית", גדודי עז א-דין אל-קסאם. מדיניות זו עוררה מחלוקת רבה בישראל ובעולם. אחת הטענות שהועלו כנגד מדיניות זו היא שהיא לא הייתה יעילה ואף השיגה את התוצאה ההפוכה בכך שהיא ליבתה את האש. כמו כן, ארגוני שמאל וארגוני זכויות אדם בארץ ובעולם טענו שהיא מהווה למעשה ביצוע גזר דין מוות ללא משפט.
עקב חוסר התקדמות הדיפלומטית במשא ומתן עם הפלסטינים, בתחילת 2001, תוך כדי האינתיפאדה, נערכו הבחירות המיוחדות לראשות הממשלה כאשר ב-6 בפברואר 2001 ניצח מועמד הליכוד, אריאל שרון אשר הקים ממשלת אחדות עם מפלגת העבודה. בשל ההחמרה במצב המדיני סירב שרון להמשיך את תהליך המשא ומתן עם הרשות הפלסטינית וניסה אף לגרום להפחתת כוחה של הרשות הפלסטינית באמצעים שונים, להראות את הקשר בינה לטרור, ולגרום לה לדה לגיטימציה בעולם.
בשנת 2002 במהלך פסגת הליגה הערבית בביירות הועלתה לראשונה הצעה לתוכנית מדינית חלופית אשר תביא לקיצו את הסכסוך הישראלי-ערבי והסכסוך הישראלי-פלסטיני (ראו היוזמה הסעודית). בהמשך גובשה ההצעה לכדי תוכנית מדינית המקובלת על כלל המדינות הערביות החברות בליגה הערבית. לפי התוכנית, כל מדינות ערב ינרמלו את יחסיהן עם ישראל ויביאו לקיצו של את הסכסוך הישראלי-ערבי בתמורה לנסיגה ישראלית מלאה משטחי רמת הגולן, רצועת עזה ויהודה ושומרון (לרבות מזרח ירושלים). כמו כן, במסגרת התוכנית נדרשה ישראל לאפשר את הקמתה של מדינה פלסטינית עצמאית, ו"למצוא פתרון צודק" לבעיית הפליטים בהתאם להחלטה 194 של העצרת הכללית של האו"ם. ישראל דחתה את היוזמה בעיקר בשל הוויתורים הטריטוריאליים הרבים הכרוכים בה.
לאחר תקופה של הבלגה יחסית מצד ישראל, בסופו של דבר, לאחר פיגוע התאבדות קטלני במיוחד במלון פארק בנתניה אשר אירע ב-27 במרץ 2002 בו נרצחו 30 ישראלים, הורה שרון על יציאה למבצע חומת מגן. המבצע היה מבצע צבאי בקנה מידה גדול אשר נמשך בין ה-29 במרץ ל-10 במאי 2002 ואשר במהלכו פעלו כוחות צה"ל בערים הפלסטיניות באזור הגדה המערבית. מבצע זה והמבצעים הצבאיים שבאו אחריו תרמו באופן משמעותי להפחתת פיגועי הטרור הפלסטיניים בישראל.
במסגרת המאמצים להילחם בטרור הפלסטיני, ביוני 2002 החלה ישראל להקים את גדר ההפרדה לאורך גבולות הקו הירוק עם הגדה המערבית. לאחר שגדר ההפרדה הוקמה, פיגועי ההתאבדות ומתקפות הטרור הפלסטיניות בישראל ירדו ב-90%. עם זאת, גדר ההפרדה הפכה למכשול מהותי נוסף בפתרון הסכסוך הישראלי-פלסטיני.