בשלב זה הודיע יוסי ביילין, סגנו של פרס במשרד החוץ, לפרס על קיום ערוץ משא ומתן חשאי עם הנהגת אש"ף, שעקף את המסלול "המוסדי" עם המשלחת הירדנית-פלסטינית לוועידת מדריד. אישים המקורבים לערפאת החלו במגעים עם נציגים ישראלים המקורבים לביילין (יאיר הירשפלד ורון פונדק), בתיווכו של הנורווגי טריה לארסן. בשיחות אלו הושגו הבנות והסכמות מתקדמות בהרבה מאשר אלו שהושגו במסלול מדריד. פרס הביא את רבין בסוד העניין, והשניים הסכימו להעלות את דרג השיחות, ולשלוח את מנכ"ל משרד החוץ אורי סביר להמשך השיחות.
במאי 1993 המשיך סבב שיחות נוסף, ולבסוף הגיעו הצדדים להסכם. על ההסכם המקורי חתמו פרס ומחמוד עבאס (אבו מאזן) בחשאי באוסלו ב-20 באוגוסט 1993, ועל כן ההסכם ואלו שבאו אחריו זכו לשם "הסכמי אוסלו". לאחר החלפת מכתבי ההכרה ההדדית בין רבין ליאסר ערפאת, חתמו פרס ועבאס ב-13 בספטמבר על "הצהרת העקרונות בדבר הסדרי ביניים של ממשל עצמי", בטקס חגיגי שנערך על מדשאות הבית הלבן בהשתתפות רבין, ערפאת ונשיא ארצות הברית ביל קלינטון. על צעד זה זכה פרס, יחד עם רבין וערפאת, בפרס נובל לשלום לשנת 1994. חתימת ההסכם עם ערפאת, שהיה במשך שנים אויבה בנפש של מדינת ישראל, והיה אחראי לכמה מהפיגועים המרים ביותר נגד אזרחיה, הביאה לפילוג קשה בעם. גל של פיגועי התאבדות שגרם להרוגים רבים, הביא גם הוא לכך שרבין, ועמו פרס, הואשמו על ידי גורמים קיצוניים בבגידה, ובחלקים מן הציבור החלה התנגדות חריפה למהלכים אלה.
פרס השתתף גם בגיבוש הסכם השלום בין ישראל לירדן. זמן קצר אחרי חתימת הסכם אוסלו הראשון, פגש פרס את הנסיך חסן, אחיו של המלך חוסיין, בבית הלבן. ב-2–3 בנובמבר 1993, נסע בחשאי לעמאן וניהל משא ומתן עם המלך חוסיין, ובסופו הגיעו השניים להסכם בן 4 עמודים עליו חתמו בראשי תיבות. עם שובו התראיין פרס בטלוויזיה על הבחירות המוניציפליות שהתקיימו יום קודם. בחדר האיפור הוא פלט: "זכרו את השלושה בנובמבר". בראיון עצמו שאל אותו מנשה רז למה הייתה הכוונה באמירה הזו. פרס התחמק, אך פליטת הפה כבר חשפה את הסיפור. המלך חוסיין זעם על ההדלפה, וניתק מגע, ורבין בתגובה מידר את פרס מהמשא ומתן עם ירדן, ונטל את המושכות לידיו עד לחתימת הסכם השלום באוקטובר 1994.
ב-1993 הוציא לאור פרס את ספרו "המזרח התיכון החדש", אותו כתב ביחד עם אריה נאור. בספר פרש את חזונו לגבי עתיד המזרח התיכון, שבו אינטרסים כלכליים ועל-לאומיים ייגרמו לשמירה על השלום באזור. שם הספר הפך לביטוי שגור, בייחוד בפי אנשי הימין, המשתמשים בו כדי לנגח את מה שהם רואים כפנטזיות בלתי מציאותיות לגבי המצב במזרח התיכון.
ראש הממשלה: כהונה שנייה (1995-1996).
ב-4 בנובמבר 1995 נרצח ראש הממשלה יצחק רבין בתום עצרת השלום הגדולה בכיכר מלכי ישראל, שבה השתתף גם פרס. הממשלה, שנתכנסה עוד באותו הלילה, בחרה באופן טבעי פה אחד בפרס לראש הממשלה בפועל, וב-22 בנובמבר הציג את ממשלתו החדשה בכנסת, שבה שימש גם שר הביטחון. רבים ציפו כי יבחר באהוד ברק או באישיות ביטחונית אחרת לשמש לצדו שר הביטחון, אך כבן-גוריון וכרבין, העדיף פרס לשמור את התפקיד לעצמו.
בנובמבר ובדצמבר ביצעה ממשלת פרס נסיגה מהערים הפלסטיניות ביהודה ושומרון, לפי הסכם אוסלו ב' (למעט בחברון). אחרי תום הנסיגה ניסה פרס לבדוק את הסיכוי לחידוש המשא ומתן עם סוריה, אולם כאשר קיבל את הרושם שאין סיכוי להשלמתו במהירות, החליט להקדים את הבחירות לכנסת בכמה חודשים – מאוקטובר למאי.
הפופולריות שהייתה לפרס לאחר רצח רבין לא נותרה גבוהה לזמן רב. בתחילת ינואר 1996 אישר פרס את חיסול "המהנדס" יחיא עיאש, מי שהיה אחראי על גל פיגועים בישראל, ונחשב לאחד המבוקשים הבכירים ביותר ברשות הפלסטינית. בתגובה ביצע חמאס בין 21 בפברואר ל-4 במרץ ארבעה פיגועי התאבדות בירושלים, באשקלון, ובתל אביב, שבהם נהרגו למעלה מששים איש, וכתוצאה מהם התערערה תחושת הביטחון של הציבור. פרס נתפס בעיני רבים כמי שאין לו תשובה לגל הטרור. יוזמתו, לכנס את כל מנהיגי העולם ל"ועידת עושי השלום" בשארם א-שייך ב-13 במרץ 1996 – ועידה שאליה הגיעו נשיא ארצות הברית ביל קלינטון, נשיא רוסיה בוריס ילצין, נשיא צרפת ז'אק שיראק ויאסר ערפאת – נתפסה על ידי רבים כתרגיל ביחסי ציבור, יותר מאשר צעד ממשי נגד הטרור שפרץ באותו החודש.
בתחילת אפריל ירה חזבאללה מטחי קטיושות על יישובי גבול הצפון של ישראל. תחילה החליט פרס להבליג, בייחוד לנוכח חג הפסח והפגיעה בתיירות הצפויה בחג. אולם כאשר מטחים אלה התגברו, החליט פרס שלישראל אין בררה אלא להגיב, והורה על פתיחת מבצע "ענבי זעם" ב-11 באפריל. ב-18 באפריל הרג פגז תותח ישראלי, שנורה לעבר משגרי קטיושות, יותר ממאה פליטים שהצטופפו במחנה או"ם בכפר קאנא, שסמוך אליו פעלו אנשי חזבאללה. בתחילה היה נראה שישראל תפסיק את המבצע, אך פרס החליט להמשיכו, ורק ב-27 באפריל הוא הופסק, כאשר הושגו בעקיפין הבנות בין ישראל, לבנון וסוריה. מבצע זה עזר רק במעט, אם בכלל, לחזק את מעמדו כדמות "ביטחונית", שהתערער עקב פיגועי חמאס, והתקפות חזבאללה. אולם מצד שני תקרית כפר קאנא עוררה עליו את זעמם של ערביי ישראל.
מערכת הבחירות בשנת 1996, שבה התמודד פרס מול מועמד הליכוד בנימין נתניהו, הייתה הראשונה שהתנהלה לפי חוק הבחירה הישירה. במערכת הבחירות ניסה פרס להסתמך על גל האהדה כלפיו וכלפי המפלגה בעקבות רצח רבין, מבלי להראות כמי שמנצל את הרצח, וניסה גם להתגבר על הפער בין הדימוי של רבין כ"מר ביטחון" לבין הדימוי שלו. פרס הרבה להופיע בבטלדרסים צבאיים, וסיסמת הבחירות שלו הייתה "ישראל חזקה עם פרס", שנבנתה על משקל הסיסמה "ישראל מחכה לרבין".
אולם פרסומאי הליכוד, בעצתו של ארתור פינקלשטיין, כבשו את סדר היום כאשר הראו בתשדירי הבחירות את פגיעות הפיגועים והקטיושות, וחזרו שוב ושוב על סיסמאות כמו "אין שלום, אין ביטחון, אין סיבה להצביע פרס" ו"פרס יחלק את ירושלים". שוב ושוב חזר תשדיר אחד, בו נראית זכוכית, המנופצת וחושפת את תמונתו של פרס הולך יד ביד עם ערפאת (תמונה שצולמה בוועידה הכלכלית בדאבוס). גם בעימות הטלוויזיוני, בו פרס ניסה להתעלם מנוכחותו של נתניהו, פרס נראה מבוגר ועייף מול נתניהו הצעיר ובעל ההופעה הטלוויזיונית המלוטשת.
בליל הבחירות, 29 במאי, הראו המדגמים על שוויון, ועל יתרון קל לפרס, בתחום הטעות הסטטיסטית. העובדה שהמדגמים סירבו להכריז על המנצח, לא הפריעו לאנשי פרס להתחיל לחגוג. רק בשעת לפנות בוקר, כשרוב הציבור בישראל כבר ישן, החלו לזרום תוצאות האמת, והמדגמים היו לטובת נתניהו. עם עלות הבוקר התברר שנתניהו מוביל ברוב קטן וכנראה ינצח בבחירות. כעבור יום נוסף, עם סיום ספירת קולות החיילים, התברר שפרס הפסיד בהפרש של כשלושים אלף קולות, כאחוז אחד ממספר המצביעים.
פעילות פוליטית מאוחרת (1996-2007).
אחרי הפסדו בבחירות הקים פרס את מרכז פרס לשלום, שנועד לקדם את השלום על ידי עידוד שיתוף פעולה בין ישראל לשכנותיה, לפי חזון "המזרח התיכון החדש" שלו. הוא נותר בתפקיד יושב ראש מפלגת העבודה ויושב ראש האופוזיציה, אך בראיון טלוויזיוני עם ניסים משעל בספטמבר 1996 הודיע כי אין בכוונתו להתמודד עוד על ראשות מפלגת העבודה, בבחירות המקדימות ביוני 1997 שבהן התמודדו יוסי ביילין, שלמה בן עמי, אפרים סנה ואהוד ברק. ראיון זה נתפס על ידי רבים כמעין הודעת פרישה. אחרים ראו בו מעין אמירה כי יהיה מי שיהיה אשר יזכה בבחירות המקדימות, פרס יימצא דרגה אחת מעליו, כמדינאי בכיר.
יחסיו של פרס עם ברק, המנצח בבחירות המקדימות, היו בעייתיים מתחילתם. ברק ראה עצמו כמוביל היחיד של מפלגת העבודה אל ניצחון עתידי בבחירות, בעוד שפרס סירב להיעלם, והמשיך לדרוש עמדת השפעה. ניסים זווילי יזם במאי 1997 הצבעה במרכז המפלגה, על הצעה למנות את פרס ל"נשיא מפלגת העבודה". ברק התנגד לכך, מחשש שמדובר בעמדת כוח שתיצור במפלגה "מחנה פרס", שיצר את צעדיו של כל יושב ראש עתידי. ההצעה כשלה בהצבעה. מאותה הצבעה זכורות שאלתו הרטורית של פרס את צירי הוועדה: "אני שומע את חבריי אומרים: 'פרס הוא לוזר'. אני הפסדתי?!" ותשובות ה"כן", החוזרות ונשנות מהקהל.
ב-1999 ניצח ברק בבחירות, שבהן הוצב פרס במקום השני ברשימת ישראל אחת, והיה ראש הממשלה. פרס נבחר לכנסת מהמקום השני ב"ישראל אחת". בתחילה ביקש להיבחר ליושב ראש הכנסת, אך לכך סירב ברק. לבסוף מינה אותו ברק ל"שר לשיתוף פעולה אזורי". נראה כי משרד זה היה תואר ריק מתוכן. שר החוץ דוד לוי סירב לוותר עבורו על סמכויות משרדו, וכך גם שרים אחרים. התפקיד שנותר למשרד הוא ייצוג ישראל בוועידות כלכליות אזוריות. רק לאחר מאבק הסכים ברק לשתף את פרס בקבינט המדיני-ביטחוני שהקים.
בשנת 2000, אחרי שעזר ויצמן התפטר מהנשיאות, החליט פרס להתמודד על התפקיד. הוא היה מועמדה של קואליציית ברק המתפוררת, אבל בשל מעמדו האישי הבטיחו לו רבים את תמיכתם. ההצבעה החשאית בכנסת לתפקיד התקיימה ב-31 ביולי, והפרשנים העריכו שפרס יזכה ללא קושי. בסיבוב הראשון זכה פרס בתמיכתם של 57 חברי כנסת בלבד, לעומת 60 למשה קצב. בסיבוב השני זכה קצב לעוד שלושה קולות, ופרס ספג הפסד צורב נוסף.
במהלך הקדנציה של ברק בראשות הממשלה, היו יחסי ברק ופרס מתוחים. ברק לא שיתף את פרס במשא ומתן המדיני, ומתח ביקורת על הסכמי אוסלו, שנקשרו בשמו של פרס. פרס, מצידו, מתח ביקורת על ברק וטען כי "הוא יביא מלחמה ולא שלום".