בחצי שנה שלקראת הבחירות ידעה ממשלת שמיר סדרת משברים: סדרת פיגועי טרור, הנודע שבהם הוא רצח הלנה ראפ; ירי קטיושות בגבול הצפון בידי חזבאללה; כלכלה מקרטעת לנוכח גל עלייה המוני, שבשיאה הגיעה למעל 200 אלף מובטלים; משבר הדיור עבור מאות אלפי העולים החדשים; פרשות שחיתות שהתפרסמו בצמרת השלטונית, דו"ח מבקר המדינה שהתפרסם לקראת הבחירות וחשף שורה ארוכה של אי-סדרים; משבר ביחסי ארצות הברית–ישראל; ואי ההתקדמות במגעים להסדר ובמשא ומתן שהתקיים בוושינגטון מאז ועידת מדריד (1991). כל הגורמים הללו השפיעו על פניית פלך בוחרים רחב בעד העבודה בהנהגת רבין לקראת הבחירות.
בעקבות ניצחון מפלגת העבודה בבחירות לכנסת השלוש עשרה שהתקיימו ב-23 ביוני, זכתה המפלגה ל-44 מנדטים, וביחד עם מרצ, חד"ש והמפלגה הדמוקרטית הערבית השיגה רוב חוסם של 61 בכנסת. בנאום שנשא כאשר נודעו תוצאות הבחירות הצהיר "אני אחליט ואני אנווט", כדי להבהיר שאין בכוונתו לחזור על מאורעות ממשלתו הראשונה. במהלך המשא ומתן הקואליציוני התנגד להרכבת ממשלה עם חמשת חברי הכנסת מן המפלגות הערביות וניהל בין לבין דיונים עם מפלגת צומת בהנהגת רפאל איתן שזכתה לשמונה מנדטים. רבין הקים את ממשלתו בקואליציה עם מרצ (12 מנדטים) וש"ס (6) ושב לתפקיד ראש הממשלה ב-13 ביולי. הוא שמר לעצמו את תיק הביטחון, ומינה את פרס לשר החוץ ולממלא מקומו ואת אברהם שוחט לשר האוצר. למנכ"ל משרדו מינה את שמעון שבס ולראש לשכתו מינה את איתן הבר.
מיד עם תחילת כהונתו של רבין נפתר משבר הערבויות בין ישראל לארצות הברית שנסוב סביב הענקת ערבויות בידי וושינגטון לישראל למען שיכון כל העולים בגל העלייה הרחב ממדינות ברית המועצות לשעבר שנמשך לכל אורך שנות התשעים. הממשל האמריקאי של ג'ורג' הרברט ווקר בוש (האב), התנה את מתן הערבויות שדרשה ממשלת שמיר בהפחתת ההתיישבות ביהודה ושומרון וחבל עזה ובאפשור פיקוח על הבנייה הקיימת. עם הזמן החמיר הממשל עם דרישותיו עד אשר דרש משמיר הפסקה מוחלטת של כל הבנייה בשטחים. שמיר לא יכול היה להיענות לדרישה זאת, שסטרה את עקרונותיו האידאולוגיים, והדבר עלה לו בקולם של מאות אלפי העולים החדשים בקלפי.
היעד המרכזי והבלתי מוצהר של הממשל האמריקאי היה להביא למפלת ממשלת הליכוד בראשות שמיר, כך שעם בחירתו של רבין מיהר הנשיא בוש להקל מהדרישות הקודמות שלו. ב-10 וב-11 באוגוסט 1992 פגש רבין בנשיא בוש, שוחח עמו ועם מזכיר המדינה ג'יימס בייקר והתחייב לצמצם עד מאוד את היקף הבנייה בשטחים. ב-11 באוגוסט נחתם הסכם הערבויות בהלוואה על סך 10 מיליארד דולר בפריסה לחמש שנים. חודשים ספורים לאחר מכן נחל בוש מפלה בבחירות לנשיאות והוחלף בביל קלינטון. במקור רבין חשש משינוי עמדה של הממשל החדש ביחס לישראל, במיוחד לנוכח התמיכה הרבה שממשל בוש האב העניק לו, אך חששות אלו פגו לאחר פגישתו הראשונה עם הנשיא קלינטון מאז שנבחר, שנערכה בבית הלבן במרץ 1993.
משא ומתן מדיני עד חתימת הסכם אוסלו.
עם תחילת כהונתו, פתח רבין במשא ומתן לשלום עם סוריה ועם הפלסטינים. תחילה תלה רבין תקוות גדולות יותר בהצלחת הערוץ הסורי, מתוך הנחה כי התנגדותו החריפה להסכם השלום של מצרים עם ישראל התרופפה לנוכח בידודה הבינלאומי של סוריה לאחר התפרקות ברית המועצות ומלחמת המפרץ בעיראק. הוא מינה את פרופ' איתמר רבינוביץ', מומחה לסוריה, כשגריר בארצות הברית. כשנודע בציבור הישראלי כי הוא נכון לנסיגה כמעט מלאה ברמת הגולן, למרות הבטחותיו כי לא יעשה כך במהלך הבחירות, פתחו תושבי הגולן במחאות וראו בכך הפרה של אמירתו מלפני הבחירות לפיה "לא יעלה על הדעת שגם בשלום נרד מרמת-הגולן". עקב כך נתן רבין את הסכמתו שעל הסכם עם סוריה יתקיים משאל עם. תגובתו בישיבת המפלגה כי המוחים "יכולים להסתובב כמו פרופלור" עוררה זעם, למרות ההבהרות כי הכוונה הייתה רק לאלה ש"חרגו מכללי הסדר הציבורי, וחברו לאנשי הימין הקיצוני של מתנחלי יש"ע".
נפתחו ערוצי שיחות חשאיים בין ישראל לסוריה במצרים ובאירופה בנוסף למגעים בוושינגטון, אך איבה, עוינות וחשדנות הדדית הקשו על התקדמות המגעים. בסתיו 1992, לנוכח התקדמות במגעים, הודיעה סוריה על נכונותה לשלום מלא עם ישראל, אך המגעים החלו להתעכב ולא הבשילו להסכם עקרונות משותף. בין נושאי המתיחות העיקריים שהעיבו על המגעים היה שאלת תוואי הגבול בהסדר השלום, כאשר סוריה דחפה להשבה של גבול הקו הירוק ובנוסף אליו גם לשליטה בגדה המזרחית של הכנסת ובמימייה בגדה הזאת. כמו כן, העמדה הסורית התעקשה להסדר שלום רב שלבי והדרגתי שייעשה במקביל להסדרים דומים של ישראל מול ירדן, לבנון והפלסטינים. רבין התנגד לכך בצורה נרחצת, והנחה את רבינוביץ' לפעול בלא פשרות על סמך הצהרתו כי: "לא ניכנס לשום דיון טריטוריאלי עם הסורים, לפני שיאמרו בקול גדול לנו ולעם בסוריה, שהשלום עבורם זו שגרירות, גבולות פתוחים ונורמליזציה."לנוכח הקרטוע של המגעים במהלך חודשים ארוכים, ב-2 באוגוסט 1993 העניק רבין התחייבות מותנית למזכיר המדינה האמריקאי וורן כריסטופר ולפיה ישראל תהיה מוכנה לנסיגה מלאה מרמת הגולן (תוואי הגבול לא נדון בהבטחה) בתמורה לעסקת חבילה כוללת עם סוריה שבמסגרתה נורמליזציה והסדרי ביטחון מלאים, כינון יחסים דיפלומטיים ומסחריים, פתיחת הגבולות למעבר אנשים וסחורות, הבטחת צורכי המים של ישראל והקמת תחנות התרעה בגולן, שיהיו מאוישות בידי כוחות אמריקאים. העריץ הסורי, חאפז אל-אסד, שלל את עקרונות תוכנית זאת והסכים לקדם הסדר שלום מינימליסטי וקר בלבד. המשא ומתן עלה על שרטון ומאמצי ממשלת רבין לא הצליחו להביא לפריצת דרך. במהלך 1994, בעקבות החתימה על הסכם אוסלו א', הביע רבין עמדות נוקשות יותר מבעבר במגעים עם סוריה, במטרה להשהות אותם עד להשלמת מתווה השלום עם הפלסטינים. במרץ 1996 הושעו המגעים. המשא ומתן בין ישראל לסוריה קפא, על אף התמיכה האמריקאית והצורך של דמשק להתקרב למערב לאחר התפרקות ברית המועצות.
בערוץ הפלסטיני העדיף רבין את הערוץ של שיחות וושינגטון עם ההנהגה של אש"ף פנים (שישב בשטחים), תוך חתירה להסכם ביניים, ושלל שיחות עם אש"ף חוץ (שישב בתוניסיה) של יאסר ערפאת, בו הוא ראה מכשול לכל הסדר. אולם למרות הבטחתו של רבין שישיג הסכם עם הפלסטינים תוך תשעה חודשים, לא התקדם המשא ומתן בשיחות וושינגטון, והטרור הפלסטיני נמשך. בדצמבר 1992 החליט רבין בעקבות חטיפת נסים טולדנו ורציחתו, לגרש ללבנון 415 מפעילי חמאס והג'יהאד האסלאמי. עתירות מהירות הוגשו לבג"ץ וזה הורה על צו ביניים לעצור את האוטובוסים עם המגורשים בדרכם ללבנון. חבר השופטים בבג"ץ התפלג בין תומכי הנשיא מאיר שמגר שנחשב "ביטחוניסט" לבין תומכי השופט אהרן ברק שראה את זכויות האדם של המגורשים כמעלה ראשונה בפרשה. רבין חשש שמחנה ברק יהפוך את החלטתו על הגירוש והורה בצעד חסר תקדים לרמטכ"ל אהוד ברק להעיד בפני בג"ץ בעד הגירוש. בסופו של דבר הגיעו השופטים ברק ושמגר לפשרה והגירוש אושר בבג"ץ.
באוגוסט 1993 חל מפנה בעמדותיו של רבין, והוא הסכים למתווה השיחות המוקדמות עם אש"ף שנוהלו באוסלו, לאור כישלון השיחות שנערכו בוושינגטון. רבין דאג להכניס לתוך מתווה אוסלו סידורי ביטחון נוספים ולהטות את ההסכמים לכיוון שיותר התאים לגישתו שהעדיפה הסדרי ביניים על פני הסדר קבע. בנוסף, ההתקדמות של המגעים באוסלו הובילה את רבין להעביר את הדגש במאמצים הדיפלומטיים מסוריה לפלסטינים. הדעות חלוקות לגבי המניע לתפנית בעמדתו של רבין. מובילי ערוץ השיחות באוסלו טענו שרבין שינה את עמדתו לאחר שהבין שלא ניתן להגיע להסדר עם אש"ף פנים, אלא רק עם בעל הבית, יאסר ערפאת. אחרים טענו שרבין נאלץ להסכים למסלול של אוסלו, לאחר ששיחות וושינגטון הוכשלו בידי משרד החוץ של ישראל, בראשותו של שמעון פרס וסגנו יוסי ביילין, והתמיכה ברבין בתוך מפלגתו הלכה והצטמצמה. בין היתר פרצו מאבקים פנימיים בתוך הממשלה בין ש"ס למרצ, בתוך מפלגת העבודה ולנוכח האשמות פליליות וחשיפת פרשיות שחיתות בקרב חברי ש"ס בממשלה. עקב המאבקים הרבים נאלצה שרת החינוך, שולמית אלוני ממרצ, להתפטר מתפקידה עקב עמדותיה והתבטאויותיה נגד ש"ס ובדבר כפייה דתית.
הסכם השלום עם ירדן.
עם החתימה בספטמבר 1993 על הסכם אוסלו א', החלו המגעים בין ישראל לירדן לתפוס תאוצה. תחילה קידם חוסיין, מלך ירדן מהלכים בוני אמון למגעים בינו להנהגה הישראלית, כגון פגישה בין יורש העצר הירדני הנסיך חסן בן טלאל ושר החוץ פרס שהתקיים בפומבי בארצות הברית. חוסיין רצה להאיץ את התקדמות המשא ומתן עם ישראל על בסיס חשש שההתקדמות בערוץ הפלסטיני עלולה לעלות על חשבון האינטרסים הירדנים במשא ומתן. את ההחלטה לקדם הסכם שלום סופי ולא רק הסכם ביניים או מהלכים מדיניים מוגבלים, קבע המלך חוסיין לאחר הסכם קהיר ב-1994, שבעקבותיו נפגש בלונדון ב-19 במאי עם רבין והחל לדון עמו על הסדר קבע. המשא ומתן נמשך כחצי שנה עד להגעה להסכם שלום.