ב-3 בפברואר קיבל בן-גוריון איגרת חריפה מאייזנהאואר: "תקותי הנמרצת היא שהנסיגה תושלם ללא דחיה נוספת. המשכת ההתעלמות ממשפט האומות, כפי שבוטא בהחלטות האו"ם, עלולה להביא כמעט בבטחה להליכים נוספים של האו"ם, שיפגעו באופן רציני ביחסים שבין ישראל ובין חברות האו"ם, לרבות ארצות הברית". בתשובתו לאיגרת זו, הביע בן-גוריון נכונות לפנות את שארם א-שייח' בתנאי שיובטח השיט החופשי, ולפנות את צה"ל מרצועת עזה, בתנאי שיושארו בה מנהל אזרחי ומשטרה ישראלית, בתיאום עם האו"ם. בנוסף לכך, הביע את כעסו: "האם אין אנו זכאים לפי מגילת האו"ם לביטחון ולחופש מהתקפות ככל אומה אחרת?... האין זכות לתושבי ישראל להיות מובטחים מרצח על ידי כנופיות טרוריסטים, המאורגנות על ידי מצרים, שהיא חברה באו"ם? האין זכות לאניות ישראל לשוט בנתיבות מים בין־לאומיים כזכות שישנה לאניות שאר האומות? באיגרתך אתה רומז על האפשרות של 'אמצעים' שיינקטו על ידי האו"ם נגד ישראל... 'אמצעים' אלה לא ננקטו אף פעם נגד מצרים, אשר במשך שנים הפרה החלטות מועצת הביטחון וסעיפי מגילת האו"ם... היש להעלות על הדעת כי ארצות הברית...תתמוך באפליה זו...?... עמנו לא ישלים עם כך לעולם, יהיה הקרבן שנצטרך להקריב אשר יהיה".
מפלגות הקואליציה, מפא"י, מפ"ם, אחדות העבודה והמפלגה הפרוגרסיבית, ערכו ב-9 בפברואר הפגנות המונים בשלוש הערים הגדולות, בססמה "נגד שיבת המרצחים המצריים לעזה, נגד הכניעה לנפט הערבי, בעד שיט חופשי במפרץ אילת ובתעלת סואץ, בעד שלום במזרח התיכון". בהפגנות השתתפו רבבות אנשים. בתל אביב הוערך מספר המפגינים ב-150,000 איש.
מגעים שניהל באותה עת שגריר ישראל באו"ם, אבא אבן, עם מזכיר המדינה ג'ון פוסטר דאלס לשם קבלת תמיכה אמריקאית לחופש שיט במצרי טיראן עלו בתוהו. ב-17 בינואר הכריז הנשיא דווייט אייזנהאואר כי ארצות הברית אינה מוכנה להעניק ויתורים נוספים לישראל.
בפברואר נשא נאום חמור בשידור רדיו לאזרחי ארצות הברית: "אם נסכים שהתקפה מזוינת יכולה להשיג את מטרת התוקף, פירוש הדבר שהפכנו לאחור את שעון הסדר הבין־לאומי... אני מאמין שלמען השלום אין לאו"ם ברירה אלא להפעיל לחץ על ישראל להישמע להחלטות הנסיגה... האם תורשה אומה שתוקפת וכובשת טריטוריה זרה לנוכח גינוי האו"ם לכפות תנאים לעצם נסיגתה?... אסור שהאו"ם ייכשל!".
ב-28 בפברואר הגישו מדינות הגוש האסייתי-אפריקאי לעצרת האו"ם הצעת החלטה להטיל סנקציות על ישראל, ורק אז הסכימה ארצות הברית להצהיר כי מפרץ אילת הוא נתיב שיט בינלאומי הפתוח למעבר ספינות כל המדינות וכי לחופיו יוצב כוח החירום של האו"ם. בעקבות זאת הכריזה שרת החוץ גולדה מאיר בעצרת האו"ם ב-1 במרץ 1957 כי ישראל תפנה את מצרי טיראן ורצועת עזה, בהנחה שכוח החירום של האו"ם יוצב בהם, וכי ישראל תשמור לעצמה, אחרי הנסיגה, את זכות ההגנה העצמית על פי מגילת האו"ם, אם ייפגע חופש השיט במצרי טיראן.
בעקבות הודעת שרת החוץ שיגר הנשיא אייזנהאואר לראש הממשלה דוד בן-גוריון איגרת בה נאמר בין השאר:
בדברים אלה היה רמז להבטחה עמומה מצד ארצות הברית לשמירת חופש השיט לישראל במצרי טיראן.
ראש הממשלה החליט לבצע את הנסיגה עד תומה. עוד בשלבי הפינוי הקודמים ביצעה ישראל שתי פעולות גדולות ברחבי סיני, האחת, "מבצע לקט" בו נלקחו שלל כלי נשק, טנקים, משאיות, אמצעי לחימה, תחמושת, ציוד מכני הנדסי וציוד צבאי של המצרים. כל השלל הרב פונה מהר ככל האפשר לישראל, ושם עבר שיפוצים. השנייה, "מבצע עמורה": בו הרס חיל ההנדסה את התשתית הצבאית והתעבורתית של מצרים בסיני (ועל כך זכה גדוד "אסף" לצל"ש רמטכ"ל גדודי ראשון בצה"ל).
בזירה הפוליטית הפנימית עוררה הנסיגה הסופית סערה. סיעות מפ"ם ואחדות העבודה החליטו, לקראת הדיון בכנסת על הנסיגה הסופית, להצביע נגד הנסיגה. כדי לא לפרק את הקואליציה החליטה הנהלת הקואליציה שלא להגיש לכנסת הצעת החלטה מטעם הקואליציה, אלא רק שכל סיעות הקואליציה, לרבות מפ"ם ואחדות העבודה, תצבענה נגד הצעת ההחלטה של האופוזיציה.
ב-5 במרץ 1957 התכנסה הכנסת לדון בנסיגה הסופית. ראש הממשלה דוד בן-גוריון אמר:
בן-גוריון הוסיף ואמר כי הודות למאבק המדיני שניהלה ישראל הכיר העולם בחופש השיט במפרץ אילת וכי:
נאומו של ראש הממשלה שהחל בשעה 9:30 בערב נמשך שעה וחצי. הנאום היה רצוף בקריאות ביניים מספסלי תנועת החרות שנענו מקריאות ביניים מצד ספסלי מפא"י. חבר הכנסת חיים לנדאו הטיח בפני ראש הממשלה: "אתה ולא נאצר הבסת את צה"ל". בן-גוריון התעלם בנאומו מקריאות הביניים.
ראשון הנואמים לאחר ראש הממשלה היה ד"ר יוחנן באדר מסיעת חרות שדיבר על "אסון הנסיגה" ואמר:
ממשלת ישראל לא המתינה יותר ובעוד הדיון בכנסת המשיך להתנהל גם למחרת, ב-6 במרץ החלו כוחות צה"ל לפנות את רצועת עזה. ב-8 במרץ הפינוי שארך 22 שעות הושלם כאשר טור של זחל"מים וטנקים, שהיוו את המשמר העורפי של הכוח המפנה, יצא את רפיח בשעה 5.00 אחר הצהרים ויחידה שוודית של כוח החירום של האו"ם נכנסה לרצועה.
באותו יום השלימו כוחות צה"ל את פינוי שארם א-שייח', שבינתיים קיבלה כבר בישראל את השם "מפרץ שלמה", כשם שהאי טיראן קיבל כבר את השם "יטבת". הפינוי הושלם כאשר רצועת החוף המזרחית של סיני נמסרה בשעה 6:00 בערב ליחידה פינית מכוח החירום של האו"ם וכשעה וחצי לאחר מכן הורד דגל ישראל מעל לתורן בשארם א-שייח' ובמקומו הונף דגל האו"ם וצה"ל מסר את המקום ליחידה הפינית. מפקד היחידה הפינית מסר לקציני צה"ל במקום כי תפקיד יחידתו הוא לפקח על מעבר חופשי של ספינות במְצרים. הרמטכ"ל רב-אלוף משה דיין נכח במעמד זה. הציוד והחיילים הועמסו על ספינות חיל הים הישראלי שהפליגו לנמל אילת. בזאת הגיע לקיצו שלטון ישראל בסיני שארך 5 חודשים. תקוות ישראל הייתה כי בעקבות הפינוי תקיים ארצות הברית את הבטחתה לקיום חופש שיט ישראלי במצרי טיראן.
עשור של רגיעה בגבול מצרים.
עם השלמת הנסיגה נותר לראות אם יישמר חופש השיט במצרי טיראן. ישראל החליטה להעביר במְצרים מטענים על גבי ספינות זרות שאינן נושאות דגל ישראל. הראשונה הייתה הספינה הדנית "בריגיטה טופט" שנחכרה על ידי חברת צים. הספינה בת 3,500 טון הטעונה במטען של חמניות ובוטנים ליצור שמן עברה ב-24 במרץ 1957 את המצרים ללא הפרעה והגיעה לנמל אילת שם נתקבלה בחגיגיות. מאילת הפליגה הספינה לנמלי אפריקה ואסיה כשהיא נושאת מטען של מלט ואשלג. חופש השיט הפך לעובדה. בעקבותיה באו ספינות רבות ולאורך זמן. המצרים נשארו פתוחים בערבותה של ארצות הברית למעבר ספינות וסחורות לישראל במשך עשר השנים שלאחר מכן.
בהמשך העבירה ישראל מטענים בספינות זרות דרך תעלת סואץ, אך שם נתקל המעבר לעיתים בקשיים. במקרה אחד הורידו המצרים ב-22 ביולי 1957 מן הספינה "בריגיטה טופט" את העיתונאי רפי נלסון ועצרו אותו למשך תקופה מסוימת, ובמקרה השני החרימו מטען המיועד לישראל מן הספינה הדנית "אינגה טופט". בפעמים אחרות עיכבו המצרים שלא לצורך ספינות אחרות שהובילו מטענים לישראל.
שלוש תוצאות חשובות נוספות באו בעקבות הנסיגה. האחת, השתרר שקט יחסי בגבול ירדן, שידע עד למבצע סיני את אחת התקופות הסוערות ביותר של פיגועים מחד ופעולות תגמול מאידך. שקט זה הופר רק בשנת 1964 עם פעולת הטרור הראשונה של ארגון הפת"ח בניסיון לבצע פיגוע במוביל הארצי.
התוצאה השנייה הייתה השקט בגבול מצרים. לאחר תקופת ביניים בחודשים אפריל, מאי ויוני 1957, בהם אירעו עדיין מספר מעשי מיקוש ונזקים לרכוש ביישובי גבול הרצועה ופגיעות אחדות בגוף ובנפש, פסקו פעולות הפדאיון והשתרר שקט בגבול ישראל-מצרים.
התוצאה השלישית והחשובה מכל – חצי האי סיני נשאר מפורז למשך עשר שנים, למעט אירוע חריג אחד כאשר ב-18 בפברואר 1960, בעקבות מידע כוזב שהעבירו הסורים למצרים כי ישראל מתכוונת לתקוף את סוריה, החלו כוחות צבא מצריים גדולים לחצות את תעלת סואץ לתוך סיני מזרחה לכיוון גבול ישראל. לאחר שצה"ל נערך במסגרת כוננות רותם והעביר כוחות גדולים של צבא סדיר ומילואים לגבול, הוציאו המצרים בתחילת מרץ את כוחותיהם מסיני.
בחודש שלאחר הנסיגה, באפריל 1957, החלה הנסיגה לשאת גם פירות מדיניים. ב-7 באפריל החזירה ברית המועצות לישראל את השגריר אלכסנדר אברמוב שהוחזר למדינתו עם פרוץ מלחמת סיני. השגריר הוחזר לישראל לפתע, ללא שום הודעה רשמית מוקדמת.
יחסים מיוחדים נשמרו בין צרפת לישראל. אהדה רבה חשו תושבי ישראל כלפי צרפת שעמדה לצדה במשבר, סיפקה לה לפני המלחמה נשק כבד, שריון ומטוסים ותמכה בה במדיניותה. שגריר צרפת בישראל באותה עת, פייר ז'ילבר, דובר העברית היה מקובל ואהוב על כל הציבור. רביעיית מועדון התיאטרון ביטאה רחשי לב אלו בשיר שאמר "תחי צרפת וישראל, בינינו אין כבר כל הבדל".
הרגשת הרווחה שחשו תושבי ישראל לאחר המאבק המדיני והנסיגה שבעקבותיו, באה לידי ביטוי במצעד צה"ל של יום העצמאות תשי"ז שנערך בתל אביב, כאשר כחצי מיליון צופים צפו בעשרות מטוסי הסילון הצרפתיים החדשים ובנשק השלל שהוצגו במצעד.
לניצחון במלחמת סיני ולשקט שהשתרר בגבול מצרים, שבא בעקבות הנסיגה, היו גם תוצאות פוליטיות. בבחירות לכנסת הרביעת שנערכו ב-3 בנובמבר 1959 זכתה מפא"י, מפלגתו של ראש הממשלה דוד בן-גוריון, ב-47 מושבים בכנסת. בצירוף המנדטים של שותפותיה, מפ"ם שזכתה ב-9 מושבים ואחדות העבודה שזכתה ב-7 מושבים, הביאו לרוב מוחלט של 63 מושבים בכנסת.