המבצע החל ב-29 באוקטובר, וב-5 בנובמבר השלים צה"ל את כיבוש חצי האי סיני כולו, כולל האיים טיראן וסנפיר. באותו יום שיגר ראש ממשלת ברית המועצות, ניקולאי בולגנין, אגרות חריפות לצרפת, בריטניה וישראל. באיגרת לבן-גוריון איים בולגנין על קיומה של ישראל: "ממשלת ישראל משחקת בצורה נפשעת וחסרת אחריות בגורל העולם, בגורל עמה היא. היא זורעת איבה כזאת לישראל בין עמי המזרח, שאינה יכולה לא להשאיר רישומה על עתיד ישראל ומעמידה בסימן שאלה את עצם קיומה של ישראל בתור מדינה". לשם "הבטחת השלום במזרח התיכון, נוקטת הממשלה הסובייטית ברגע זה אמצעים על מנת להפסיק המלחמה ולרסן התוקפים". לצד האיומים הללו, הפיצה ברית המועצות שמועה כי היא מגייסת "מתנדבים" שישרתו בצבא המצרי. ב-6 בנובמבר הקריא הרמטכ"ל דיין בפני אלפי חיילים בשארם א-שייח' איגרת מאת בן-גוריון למסדר סיום המלחמה, בה הכריז: "יטבת (טיראן) תהיה שוב לחלק ממלכות ישראל השלישית!". ב-7 בנובמבר נאם בן-גוריון בכנסת נאום ניצחון אודות "המערכה הגדולה ביותר בתולדות עמנו" ואחד המבצעים "הגדולים בתולדות העמים". הוא טען כי "מעמד הר סיני נתחדש בימינו אלה" וכי צה"ל "לא פגע בשטחה של מצרים" אלא "אך ורק בשטח חצי האי סיני". כמו כן, טען לזכותה של ישראל על האי "יטבת" (טיראן), בהסתמכו על אזכור ההתיישבות היהודית באי בכתבי פרוקופיוס. בהתייחסו ללחצי ארצות הברית וברית המועצות, טען כי אלו העדיפו "פיוסו של נאצר על שמירת החוק הבינלאומי" ועשו זאת "על חשבון ישראל", והכריז: "לא נתבטל מפני תקיפי עולם". הוא קבע בנאומו כי "הסכם שביתת הנשק עם מצרים מת" וכי "ישראל לא תסכים בשום תנאי שכוח זר" יוצב "בתחומיה או באחד השטחים המוחזקים על ידיה". סקירתו זכתה בתמיכה מלאה מצד כל הסיעות מלבד הקומוניסטים, אולם בשנת 1966 התוודה בפני חוקר שבא לראיינו, כי טעה בהשמעת נאומו בכנסת, והסביר: "הניצחון היה מהיר מדי. הייתי יותר מדי שיכור ניצחון". למחרת התקבלו תגובות נרגזות על הנאום מהעולם, ובאותו ערב הצביעה עצרת האו"ם ברוב מוחלט שעל ישראל לסגת ללא תנאים. ב-8 בנובמבר קיבל בן-גוריון שדר חריף מאוד מהנשיא אייזנהאואר, בו דרש מישראל "לחזור מטריטוריה מצרית". אל המכתב צורף שדר בעל פה בשם מזכיר המדינה דאלס, שאיים כי אם תסרב ישראל לסגת, יופסק לה כל סיוע כספי מארצות הברית, ממשלתי או פרטי, ויוטלו עליה סנקציות על ידי האו"ם. באותו יום הגיעו ידיעות רבות לגבי התערבות צבאית סובייטית. אלו הביאו לבהלה כללית בהנהגת המדינה וגם בן-גוריון חרד מפני התקפה רוסית. הוא החליט לסגת וכתב שני מכתבי תשובה לאגרות מנהיגי ארצות הברית וברית המועצות. לבולגנין כתב: "מדיניות החוץ שלנו מוכתבת על ידי צרכינו החיוניים ועל ידי שאיפתנו לשלום, ושום גורם זר אינו קובע אותה ולא יקבע אותה". לאייזנהאואר, לעומת זאת, כתב כי הוא מוכן להיענות לדרישתו לסגת. ב-9 בנובמבר קרא את אגרותיו בשידור רדיו לאומה.
ב-12 בנובמבר יצא בן-גוריון בטיסה לסיור בן יומיים בסיני. הוא נחת בשארם א-שייח' וביום השני סייר באזור עזה. הוא ניסה להאט את הנסיגה, במטרה לנסות לספח את מצרי טיראן ולהחליף את צה"ל בכוח בינלאומי במקום צבא מצרי. הוא בחר בטקטיקה של השהייה, בתקוה שככל שהזמן יעבור, יפחת הפחד מהאיום הרוסי והעולם ינקוט בגישה מאוזנת יותר כלפי ישראל. בתקופה זו תוכל ישראל להסביר את עמדתה בארצות הברית ולרכוש את דעת הקהל. ההשהיה נועדה גם להפוך את הנסיגה לקלף מיקוח תמורת הישגים מדיניים. בן-גוריון קיווה גם שלאחר פינוי חלק מסיני, יפחת הלחץ הבינלאומי והעולם ישלים עם הישארות ישראל ברצועת עזה ובמצרי טיראן. אולם הלחץ על ישראל לא פחת. ב-15 בנובמבר קיבל בן-גוריון איגרת-איום נוספת מבולגנין. עצרת האו"ם תבעה שישראל תיסוג, תוך איום בסנקציות כלכליות. הנסיגה מסיני התבצעה בשלבים, אך במקביל אישר בן-גוריון את הצעת דיין להקים היאחזויות נח"ל בשארם א-שייח' וברפיח והחיל את החוק הישראלי על תושבי רצועת עזה. הוא סירב להתפנות מהמקומות הללו ללא תנאי ובינואר 1957 הורה ללוי אשכול ולדיין להיערך לקראת סנקציות. ב-3 בפברואר קיבל מאייזנהאואר איגרת חריפה שכללה איום בסנקציות, אך סירב לדרישתו לסגת. המאבק המדיני של ישראל הפך לעימות אישי עם נשיא ארצות הברית. בסופו של דבר נאלצה ישראל לסגת מהמיצרים ומרצועת עזה. הניצחון הצבאי הגדול הסתיים אמנם בתבוסה מדינית, אולם בעקבותיו הובטח חופש המעבר לספינות והגבולות שקטו במשך עשר שנים. "מבצע סיני" הביא לפריחה ביחסי החוץ של ישראל ולגל של גאווה בקרב יהודי התפוצות. הוא חיזק את מעמדו של בן-גוריון ואת כוחה של מפלגתו.
ענייני חוץ והכור בדימונה 1957–1961.
ב-18 בינואר 1957 נאם בן-גוריון בכנס בקיבוץ גבעת חיים ובדבריו השתמעה ביקורת חריפה נגד אופי עבודתו של משה שרת במשרד החוץ. שרת תבע את עלבונו בבירור בוועדה המדינית של מפא"י, אולם בן-גוריון סירב להתנצל. בעקבות זאת, סיים שרת את חברותו עם בן-גוריון וסירב לכל ניסיונות הפיוס שלו.
ב-29 באוקטובר 1957 הושלך רימון בכנסת. הרימון התפוצץ ובן-גוריון נפצע קל מרסיסים בזרועו וברגלו. הוא אושפז בבית החולים ובמשך מספר ימים ישב ליד מיטתו מזכירו הצבאי ומקורבו נחמיה ארגוב. ב-2 בנובמבר התאבד ארגוב, לאחר שבדרכו לבית החולים בירושלים פגע ברוכב אופניים. דבר התאבדותו הוסתר מבן גוריון בעזרתם של מספר עיתונים שהדפיסו גיליון אחד של מהדורה מיוחדת, בה לא הוזכר דבר מותו של ארגוב, וגיליונות אלה הם שנמסרו לבן-גוריון. ב-5 בנובמבר בישר לו משה דיין את הבשורה הקשה וכעבור שבועיים עמד בן-גוריון דום לזכרו של ארגוב על דוכן הנואמים של הכנסת.
שנת 1958 הייתה שנה מוצלחת מאוד במדיניות החוץ של בן-גוריון.
בשנה זו הוא החל לגבש "ברית פריפרית" פרו-מערבית עם אתיופיה, איראן וטורקיה. המשותף לגוש המדינות הללו היה התנגדות להתפשטות של נאצר ולהשפעה הסובייטית. בינואר 1958 החליף בן-גוריון מכתבים עם השאה הפרסי. ב-29 באוגוסט אותה שנה, נפגש באנקרה עם ראש ממשלת טורקיה, אדנאן מנדרס, ושר החוץ פטין רישטי זורלו . בפגישה סוכם על העלאת הנציגויות הדיפלומטיות לדרגת שגרירויות.
במהלך שנת 1958 טיפח בן-גוריון בהדרגה גם את הקשרים המדיניים עם גרמניה המערבית, חרף ההתנגדות הציבורית.
בתקופה שלאחר מבצע סיני, פרחה ידידות גדולה בין צרפת וישראל. התקיים שיתוף פעולה הדוק בין שתי המדינות ששיאו אספקת נשק רב לצה"ל, ובפרט לחיל האוויר, והקמת הקריה למחקר גרעיני בדימונה. בן-גוריון ראה בכור האטומי אמצעי להבטחת קיומה של ישראל והוא הוקם בניגוד לדעתם של רוב מנהיגי מפא"י ושריה הבכירים. ב-31 במאי 1958 נתמנה שארל דה גול, כלפיו רכש בן-גוריון הערצה עמוקה, לראש ממשלת צרפת.
ב-31 בדצמבר 1957 התפטר בן-גוריון על רקע הדלפות מישיבות הממשלה והפרות של המשמעת הקואליציונית. הממשלה השמינית, שכוננה שבעה ימים מאוחר יותר, התבססה על הרכב קואליציוני זהה. במחצית שנת 1958 יזם בן-גוריון את פריצתם של צעירי מפא"י (ובראשם דיין ופרס) לצמרת המפלגה, כדי להתחיל בה תהליך הדרגתי של חילופי דורות. ב-5 ביולי 1959 בן-גוריון התפטר שוב, עקב הצבעתם של חברי סיעות מפ"ם ואחדות העבודה - פועלי ציון נגד מכירת תת-מקלעי עוזי לגרמניה המערבית. ממשלתו המשיכה לכהן כממשלת מעבר עד כינונה של הכנסת הרביעית.
ב-3 בנובמבר 1959 נערכו הבחירות לכנסת הרביעית. למערכת הבחירות שקדמה להן נבחרה למפא"י הסיסמה "הגידו כן לזקן". בן-גוריון התלהב מאוד מדרך ההסברה החדשה של חוגי בית והשתתף בעצמו באחדים מהם. הנושא העיקרי בנאומיו היה שינוי שיטת הבחירות. בזמן מערכת הבחירות הרבה להשתמש כלפי בגין בכינוי "המוקיון". ערב הבחירות ביקר בין היתר בכפר בקה אל-גרבייה – ככל הנראה ביקורו היחיד בכפר ערבי בכל שנות שלטונו. בבחירות זכתה מפא"י ב-47 מושבים – הניצחון הגדול ביותר בתולדותיה עד אז. ב-16 בדצמבר הציג בן-גוריון בכנסת את ממשלתו החדשה, בה היו חברים גם השרים החדשים משה דיין ואבא אבן.
במרץ 1960 ביקר בן-גוריון בארצות הברית, לראשונה זה תשע שנים, שם נועד עם מנהיגים יהודים, עם אלינור רוזוולט ונלסון רוקפלר, עם מספר סנטורים ועם הנשיא אייזנהאואר. ב-14 במרץ נפגש לראשונה עם קנצלר גרמניה קונראד אדנאואר במלון וולדורף אסטוריה בניו יורק, בו שהו שניהם, בדירת השרד בה התגורר הקנצלר. השיחה נמשכה קרוב לשעתיים. אדנאואר דיבר גרמנית. בן-גוריון הבין אותו אך דיבר באנגלית ודבריו תורגמו לגרמנית. בן-גוריון ביקש סיוע כלכלי: מלווה בסך חצי מיליארד דולר, שיינתן במשך עשר שנים ויוקדש לפיתוח התעשייה והחקלאות. הוא ביקש מאדנאואר "להשתתף בבניית הארץ אחרי שקודמיך גרמו לכך שאבדו לנו ששה מיליונים אחים". הוא הסביר את בקשתו בנימוק מוסרי: "שהנוער בגרמניה...ימצא סיפוק מוסרי כלשהו כשידע שעמו...עזר להתפתחותה ולעצמאותה של ישראל". אדנאואר הסכים מיד. הוא הסכים גם לבקשת בן-גוריון לספק חינם נשק לישראל. מניו יורק טס בן-גוריון ללונדון ונפגש עם ראש ממשלת בריטניה, הרולד מקמילן.