ההסכם התגבש באמצע 1994, לאחר שבמשך עשרות שנים נפגשו מנהיגי ישראל בחשאי עם המלך חוסיין, שלא הסכים לקיים איתם שיחות גלויות. ראש הממשלה רבין ושר החוץ שמעון פרס קיימו מספר פגישות עם חוסיין, והבהירו לו כי לאחר שנחתם ההסכם עם אש"ף, עלולה ירדן להישאר "מחוץ למשחק". חוסיין נועץ בנשיא מצרים חוסני מובארכ, שעודד אותו להגיע להסכם, ונשיא סוריה חאפז אל-אסד שעודד את חוסיין לקיים שיחות עם ישראל, אך לא לחתום על הסכם. לאחר פגישה בין פרס לבין המלך חוסיין בנובמבר 1993, בה סוכמו ראשי פרקים למשא ומתן כמו גם הפרמטרים לשלום בין ישראל וירדן, פרס הדליף בעקיפין על דבר קיומה של הפגישה לתקשורת, נגד ההסכמות שהיו לו עם המלך. על פי בקשתו של המלך חוסיין, רבין הדיר את פרס מן המשא ומתן עצמו על חוזה השלום הסופי כיוון שלא שמר על דיסקרטיות, בשונה מרבין עצמו, שהשאיר את המגעים זמן רב גם ללא ידיעתם של חבר יועציו הקרובים וביניהם שמעון שבס ואמנון רובינשטיין.
במאי נפגשו רבין וחוסיין פעם נוספת, והסכימו כי השיחות יתקיימו בגבול ישראל-ירדן ולא בוושינגטון, יהיו ישירות, דו-צדדיות וללא כל מעורבות חיצונית, גם לא אמריקאית. המלך חוסיין מיהר לקדם את המגעים מתוך החשש שבמשא ומתן בין ישראל לאש"ף יושגו הסכמות הנוגעות לירושלים ולגבול בין הגדה המערבית למזרחית, הסכמות שעלולות לפגוע במעמדה של ירדן. רבין הסכים לכל הנקודות וקידם את האינטרס של ירדן בארצות הברית, שהאחרונה תסיים את החרם הכלכלי והצבאיח שהטילה על ירדן מאז מלחמת המפרץ.
בתיאום עם רבין, הנשיא האמריקאי קלינטון לחץ על חוסיין להצטרף למשא ומתן לשלום, ובין השאר הבטיח לחוסיין למחוק את חובותיה של ירדן לארצות הברית ומכירה של להק מטוסי ג'נרל דיינמיקס F-16 פייטינג פלקון. בחודשי הקיץ נערכו שיחות בין ישראל לירדן, שהפכו עד מהרה לגלויות, עם פגישת רבין, חוסיין וקלינטון בבית הלבן ופרסום "הצהרת וושינגטון" שסיימה את מצב הלוחמה בין שתי המדינות. המתווך האמריקאי נכנס לעומק הקורה על לכדי רישום טיוטת מסמך ישראלי-ירדני משותף. רבין וחוסיין גם יחד הביעו הסתייגות מהמסמך, בעיקר מהפרוטוקול הצבאי שלו, ופעלו להוריד את האפשרות מן הפרק בלי לפגוע ברצונו הטוב של ממשל קלינטון. ב-14 בספטמבר 1993 נחתם סדר יום מוסכם למשא ומתן בין ישראל וירדן וב-25 ביולי 1994 הייתה "הצהרת וושינגטון", שנערכה במדשאות הבית הלבן, ובה הכריזו שני הצדדים על היותם קרובים להשלים את הסכם הקבע.
נושא מחלוקת מרכזי נסוב על שטח בן 380 קמ"ר בערבה על גבול ישראל-ירדן שהממשל הירדני טען לריבונות עליו. בסופו של יום הוסכם על מסירת 300 קמ"ר מתוך השטח המסוכסך כפשרה. נהריים הוגדר כאזור חיץ המאפשר שהייה של שתי המדינות. רבין דרש לקדם הסכם שלום ונורמליזציה מוחלטת ביחסים, ולא שלום קר. מטרה זאת אכן הושגה, בין היתר עקב הטלות ההדדית בשאלת המים, במסגרתה ישראל התחייבה להעמיד לרשות ירדן 50 מיליון מ"ק מים מדי שנה מהכנרת ולחלוק את מימי הירמוך כך שירדן תקבל 3/4 ממנו.
במהלך המשא ומתן עם ירדן הוזמנו רבין והמלך חוסיין לנאום בפני מושב משותף של שני בתי הקונגרס האמריקאי בגבעת הקפיטול. בנאומו של רבין התפרסם בעיקר הקטע הבא:
ב-26 באוקטובר 1994 חתם רבין על הסכם השלום בין ישראל לירדן במעבר הגבול החדש מצפון לאילת בטקס ששודר בשידור חי ברחבי העולם. אורח הכבוד היה נשיא ארצות הברית, ביל קלינטון. ההסכם פתח את שערי ירדן בפני אנשי עסקים ותיירים מישראל. בניגוד להסכמי אוסלו, זכה ההסכם עם ירדן לתמיכה רחבה, ורק מעט חברי הכנסת לא הצביעו בעד אישורו (בהם אריאל שרון, שנמנע). לאחר חתימת הסכם השלום עם ירדן שבה התרכזות גבוהה יותר במשא ומתן מול סוריה. אסד שמר על מדיניות המיקוח הקודמת שלו, הוא דרש את חלקה המזרחי של הכנרת כקלף מיקוח כדי להשיג את כל רמת הגולן (בפועל כל הכנרת נכללה בשטחי המנדט הבריטי על ארץ ישראל וסוריה כבשה את הגדה המזרחית של הימה לאחר מלחמת העצמאות). קשיים נוספים במגעים מול סוריה נגעו להתנגדות בדעת הקהל הישראלית לוויתור על הגולן ושאלת הסדרי הביטחון בגבול שיוסכם.
לנוכח המגעים עם סוריה ושאלת הריבונות על הגולן, אביגדור קהלני ועמנואל זיסמן ממפלגת העבודה איימו להתנתק מן הממשלה ומן המפלגה ולהקים את מפלגת "הדרך השלישית" שכל מטרתה לשמור על הריבונות הישראלית ברמת הגולן. במקביל נעשה ניסיון כושל לקדם את המגעים עם סוריה דרך שיחות של ראשי הדרג הצבאי בוושינגטון, הרמטכ"ל ברק וחיכמת שיהאבי. מגעים אלו לא הבשילו לפריצת דרך אלא רק הובילו לבירור עומקו של הפער בין העמדות. כישלון המגעים של ראשי הדרג הצבאי הוביל לקיפאון דה פקטו במגעים עם סוריה.
אירועי חוץ וביטחון נוספים.
חודשים ספורים לאחר התמנה רבין לראש ממשלה התרחש אסון צאלים ב'. ב-5 בנובמבר 1992, בבסיס צאלים שבנגב, בעת שחיילי סיירת מטכ"ל התאמנו על מודל לביצוע התנקשות בחיי נשיא עיראק, סדאם חוסיין, קרתה תאונת אימונים וירי דו-צדדי הביא למותם הטראגי של חמישה חיילי סיירת מטכ"ל.
עקב הקיפאון במגעים להסדר מול סוריה באמצע 1993, אסד החל לפעול בניסיון ללחוץ על ישראל להתפשר בעמדותיה דרך לחץ צבאי של ארגונים פרו-סוריים בלבנון על רצועת הביטחון. ב-25 ביולי 1993, לאחר הסלמה בגבול הצפון שבה נהרגו שישה חיילים ויישובי הצפון הותקפו ברקטות על ידי ארגון חזבאללה והחזית העממית לשחרור פלסטין, הנתונה להשפעתה של סוריה, הורה ראש הממשלה רבין לרמטכ"ל ברק לצאת למבצע דין וחשבון. במהלך המבצע הותקפו כפרי חזבאללה רבים בידי תותחים, טנקים ומטוסי חיל האוויר, שזרעו בכפרים הרס רב. המבצע הופסק אחר שבעה ימים, לאחר שהושגו הבנות בין ישראל לחזבאללה. לקראת החתימה על הסכם אוסלו א' הייתה עלייה בכמות הפיגועים שהתרחשו בתוך שטחי הקו הירוק.
ב-15 באוקטובר 1993 ביקר יצחק רבין באינדונזיה ופגש את נשיאה סוהארטו. ביקור הקצר התקיים בנוכחות מתורגמנית, בזמן תפילת יום השישי. בישראל פורסם שסוהארטו חשש שמא יראה הציבור היוצא מן המסגדים את יצחק רבין. תוצאת הביקור הייתה ראשית תיירות ישראלית אל אינדונזיה החל משנת 1994. במקביל, ישראל כוננה יחסים דיפלומטיים עם תוניסיה ומרוקו (מיד לאחר חתימת הסכם אוסלו א' במדשאת הבית הלבן בוושינגטון, רבין נסע למרוקו ונפגש עם המלך חסן השני, צעד שסימל את התמיכה של העולם הערבי בהסכם). באוקטובר 1994 השתתפה ישראל בוועידת הפסגה הכלכלית בקזבלנקה אשר עסקה בשיתופי פעולה כלכליים בין ישראל לשכנותיה. מרוקו בהנהגתו של המלך חסן השני גם ניסתה ללא הצלחה לקדם את המגעים בין ישראל לסוריה, ולהביא לפגישה בין רבין לאסד. בעקבות החתימה על הסכם אוסלו א', בנובמבר 1993 ביקר בישראל שר החוץ של טורקיה, חכמת צ'טין, וחתם על מזכר שיתוף פעולה עם ישראל. בין 1992 ל-1997 נחתמו חמישה הסכמים צבאיים בין צה"ל לצבא טורקיה וישראל בהנהגת רבין תרמה לכניסת טורקיה לשורות קבוצת עבודה שעסקה בבקרת נשק וביטחון אזורי. רבין ניסה גם לקדם מגעים והתקרבות זהירה ביחסי ישראל–ערב הסעודית במקביל לתהליך השלום.
בשל מעורבותו של מוסטפא דיראני בשביית רון ארד אישר רבין, בהמלצתם של ראש אמ"ן, האלוף אורי שגיא, והרמטכ"ל אהוד ברק, את מבצע עוקץ ארסי, שנערך בליל 21 במאי 1994, ובו חטפה סיירת מטכ"ל, את דיראני מביתו שבכפר קסר נבא, שבעמק הבקאע בדרום לבנון. ב-14 באוקטובר 1994, לאחר שהתקבל מידע על מקום הימצאו של החייל החטוף נחשון וקסמן, אישר רבין את פעולת ההשתלטות של סיירת מטכ"ל, בפיקוד שחר ארגמן על הבית בכפר ביר נבאלא בו הוחזק החטוף. כוח הסיירת נכשל בניסיון החילוץ של החייל נחשון וקסמן, בפעולה נהרג וקסמן וכן קצין היחידה ניר פורז ונפצעו מספר לוחמים בהם ארגמן עצמו, שנפגע מרסיסים בידו. לאחר כישלון הפעולה התייצב רבין אל מול התקשורת ולקח אחריות מלאה על האירוע ותוצאותיו. באותו השבוע של הפעולה בוצע הפיגוע בקו 5 ברחוב דיזנגוף בתל אביב, שהיה פיגוע ההתאבדות הגדול ביותר עד לאותה העת. בעקבות הפיגוע הוטל סגר על השטחים ובית משפחתו של המחבל נהרס בידי צה"ל באישורו של בג"ץ.
ב-27 בדצמבר 1994 נפגש רבין בחשאי עם קאבוס בן סעיד אאל סעיד, סולטאן עומאן, שהיה בעל קשרים חשאיים עם ישראל זה שנים רבות. בפגישתם הדגיש קאבוס כי ארצו, כמו גם חלק נרחב מן העולם הערבי, רואים בישראל גורם המסוגל לבלום את ההשפעה המהפכנית של איראן השיעית. לפי רבין, חשיבות המפגש היא שהוא העניק לישראל "רגל על הקרקע" במפרץ הפרסי.
במחצית הראשונה של 1995, רבין ביצע סדרת מינויים פרסונליים. לצד שינוי מינויי שרים בתוך הממשלה, הוא מינה את צבי אלדרוטי כמנכ"ל משרדו במקום שמעון שבס. במסגרת כהונתו כשר ביטחון, רבין התיר את עיקר הטיפול בביטחון שוטף ובתפקוד של צה"ל בידי סגנו, מרדכי גור, והרמטכ"ל ברק. עוד באותה העת פרש ברק מתפקידו והוחלף כרמטכ"ל בידי אמנון ליפקין-שחק. חודשיים לאחר מכן פרש ראש השב"כ יעקב פרי ורבין מינה במקומו את כרמי גילון. ביולי 1995, עקב מחלתו בסרטן סופני, התאבד סגן השר גור. רבין וגור היו ידידים ורבין התאבל על מותו ואמר על ביצועיו בתפקידו האחרון: "הוא ידע להופיע בשם מערכת-הביטחון לפני כל חלקי העם גם במציאות של מחלוקת בעם". לאחר תקופת צינון בת שלושה חודשים של אהוד ברק, מינה אותו רבין ביולי לשר הפנים בממשלתו.
ב-26 באוקטובר 1995, אנשי מוסד מיחידת 'כידון' התנקשו במנהיג הג'יהאד האסלאמי הפלסטיני, פתחי שקאקי, במקום שהייתו במלטה.
חתימת הסכמי אוסלו.