משלוש מטרות המבצע שהציג בן-גוריון בנאומו, ושלדבריו שלושתן עתידות להתקיים, מומשו לבסוף רק שתיים: השמדת הכוח המצרי שאיים על ישראל וחופש השיט במפרץ אילת. אולם בעתיד לבוא יתברר כי לא הושג "שחרור שטח המולדת שנתפס על ידי המצרים", כשכוונתו של בן-גוריון הייתה לרצועת עזה, ואילו חופש השיט בתעלת סואץ הושג רק בחלקו, באמצעות העברת סחורות לישראל בספינות זרות, תוך הפרעות ושיבושים מצד המצרים.
הנסיגה והמאבק המדיני.
צה"ל לא החל בנסיגה מיד לאחר הודעת ראש הממשלה, אלא המתין עד התארגנותו של כוח החירום של האו"ם. ב-15 בנובמבר התחיל תהליך הנסיגה. ביום זה הגיעו למצרים כוחות החלוץ של כוח החירום של האו"ם. באותו יום הגיעה לממשלת ישראל איגרת נוספת של ניקולאי בולגנין. בנוסף לדרישה החוזרת לנסיגה באה הפעם דרישה חדשה – כי ישראל תשלם פיצויים למצרים. האיגרת באה בתשובה לאיגרתו של ראש הממשלה דוד בן-גוריון מה-8 בנובמבר ובולגנין התנצח בה עם טענותיו של בן-גוריון, וטען כי לא מדינות ערב הן התוקפניות, אלא ישראל היא התוקפנית. האיגרת נשלחה לאחר שבן-גוריון כבר הודיע על נסיגת כוחות ישראל ממצרים ועל כן נימתה פחות חריפה מזו של איגרתו הקודמת של בולגנין. הוא ציין כי ברית המועצות קיבלה לתשומת לבה את הסכמת ישראל להוציא כוחותיה ממצרים, אך עם זאת הדגיש את הצורך "לאחוז באמצעים שימנעו פרובוקציות חדשות מצד ישראל".
כעבור יומיים השיב בן-גוריון לאיגרת וכתב כי מצרים היא זו שממנה מגיעים פיצויים למדינת ישראל על הפלישה בשנת 1948, על החרם הכלכלי, על ההסגר הימי, על מאות הנרצחים הישראלים מפעולות הפדאיון ועל הנזקים שנגרמו על ידם.
ממשלת ישראל האמינה עדיין כי אפשר להתמקח לא רק על קצב הנסיגה אלא גם על היקפה, וכי ניתן יהיה לשמור על הישגים טריטוריאליים מסוימים, בעיקר על רצועת עזה, שלה קרא בן-גוריון בנאומו הלילי "שטח המולדת שנתפס על ידי המצרים", ועל הדרישה שייאסר על צבא מצרים לחזור לשטחים שיפונו. נציגי ישראל ערכו בארצות הברית מבצעי הסברה רחבים והצליחו לגייס לטובת דרישות ישראל קולות רבים בקונגרס האמריקאי ובתקשורת, אבל ממשלו של הנשיא אייזנהאואר, שהבחירות היו כבר מאחוריו, לא הושפע מכך והתעקש על נסיגה ישראלית מלאה. הממשל סירב לתמוך בדרישת ישראל לקשור את הנסיגה עם הסכם ישראלי-מצרי על הפסקת הלוחמה, ונציגיו באו"ם תמכו במזכיר האו"ם דאג המרשלד שתבע נסיגה ישראלית מלאה, כולל מעזה, לפני כל משא ומתן על הסדר.
כבר ב-11 בנובמבר וב-12 בנובמבר התחוללו התפרעויות ברפיח, לאחר שנערכו חילופי כוחות בין יחידות צה"ל שהחזיקו בעיר והתושבים סברו כי צה"ל עומד להתפנות מן העיר. מיריות חיילי צה"ל לעבר המתפרעים נהרגו ונפצעו כ-30 מן התושבים.
כדי לחזק את מעמדה של ישראל ברצועת עזה החלו פעולות ממשל מזורזות ברצועה; משטרת ישראל התמקמה בערי הרצועה, אורגנו עבודות צבוריות, סופקו מוצרי מזון במחירים מוזלים וב-26 בנובמבר כוננה מועצת עיר חדשה בעזה בראשותו של נכבד מקומי בשם רושדי אל-שאווה, מי שכיהן בעבר כראש עיריית עזה בשנים 1939–1951. בסוף נובמבר חודשה תנועת האוטובוסים בין עזה לבין ח'אן יונס ובית חאנון.
הלך הרוח במדינה היה כי פעולות ממשל אלו תחזקנה את אחיזתה של ישראל ברצועה וישראל תמשיך להחזיק בה. בעיתון "דבר" מ-27 בנובמבר 1956 הופיע תיאור אידילי של החיים בעזה תחת שלטון ישראל:
במקביל המשיכה ישראל במאמצים מדיניים להגיע לידי הסכמה בדבר השארתה של רצועת עזה בשלטון ישראל.
ב-22 בנובמבר הודיעה שרת החוץ גולדה מאיר למזכיר האו"ם דאג המרשלד כי כוחות ישראל נסוגו כבר "לכל אורך חזית סיני במקומות שונים ובמרחקים שונים".
במשך חודש דצמבר 1956 נמשכה נסיגה איטית של כוחות צה"ל מסיני, תוך לחץ כבד של האו"ם להחיש את הנסיגה. מזכיר האו"ם דאג המרשלד הודיע באיגרת לשרת החוץ גולדה מאיר כי "בשום פנים ואופן לא ארשה עיכוב הפינוי בהתאם לדרישתה הבלתי מסויגת וללא תנאים של העצרת". ב-2 בדצמבר הודיעה ישראל לאו"ם כי הושלם הפינוי של 50 הקילומטרים הראשונים מזרחית לתעלת סואץ כולל מעבר המיתלה. ב-5 בדצמבר חצה גדוד יוגוסלבי מכוח האו"ם את תעלת סואץ והחל לנוע לעומק סיני. ב-8 בדצמבר הודיעה ברית המועצות כי לאור הפינוי של הכוחות הבריטיים, הצרפתיים והישראלים, לא יישלחו מתנדבים סובייטיים למצרים. בזאת הוסר איום ההתערבות הצבאית הישירה של ברית המועצות באזור, במסווה של משלוח מתנדבים, שהיה בין הסיבות שהביאו להחלטת הנסיגה הישראלית. ב-17 בדצמבר החל צה"ל לפנות כוחותיו ל-25 קילומטרים נוספים.
תוך כדי הנסיגה האיטית עשתה ישראל מאמצים להגיע להסכמה עם האו"ם וארצות הברית להשיג הבטחה כי צבא מצרים לא יחזור לשטחי סיני שיפונו, אך ללא הצלחה. ב-3 בדצמבר הודיעה שרת החוץ גולדה מאיר בשידור טלוויזיה בארצות הברית כי ישראל מנהלת משא ומתן עם האו"ם בדבר נסיגה סופית מרצועת עזה, אך דורשת התחייבות כי כוחות צבא מצרים לא יחזרו בדיוק לאותם מקומות בהם היו לפני המבצע.
במקביל המשיכה ישראל להיאחז ברצועה, כוננה מועצת עיר בח'אן יונס, פתחה סניף דואר בעזה וחידשה את הלימודים בבתי הספר בעיר. ב-19 בדצמבר הצהיר דוד בן-גוריון לעיתון הניו יורק טיימס: "בשום פנים ואופן אין להחזיר את המצרים לעזה. אנו לא ניתן להם לחזור". כן המליץ בן-גוריון בראיון זה על פירוז סיני ובינאום מצרי טיראן.
בן-גוריון חזר על דברים אלה באותו יום כשהודיע בכנסת על התנגדותה של ישראל לחזרת המצרים לרצועה, והצהיר כי: "ישראל לא תסכים בשום פנים ואופן לשוב הפולש המצרי לרצועה זו".
ב-29 בדצמבר נפגשה שרת החוץ גולדה מאיר עם מזכיר המדינה האמריקאי ג'ון פוסטר דאלס בוושינגטון הבירה והוא הביע בפניה את מורת רוחו על מה שכינה "הניסיון להציג תנאים להחלטת הפינוי של האו"ם" והדגיש בפניה בתוקף כי על ישראל לבצע נסיגה מלאה לקווי שביתת הנשק.
ב-8 בינואר 1957 השלימה ישראל את פינוי כוחותיה מכל השטחים שכבשה ממערב לאל עריש, אך ניסתה לעכב את המשך הנסיגה בדרישה לערבויות בינלאומיות נגד תוקפנות מצרית חדשה בטרם תמשיך לסגת, אך ארצות הברית תבעה כי קודם תושלם הנסיגה עד לקווי שביתת הנשק ורק אז יהיה דיון בערבויות.
בישראל התעורר ויכוח ציבורי ומפלגתי בשאלת המשך הנסיגה. מפלגות האופוזיציה, ובראשן תנועת החרות בהנהגתו של מנחם בגין, התנגדו להמשך הנסיגה. גם מפלגת אחדות העבודה, שהייתה חברה בממשלה, התנגדה להמשך הנסיגה מצפון סיני והצביעה נגדה בממשלה, אך בהצבעה בכנסת, ב-15 בינואר, שמרה על משמעת קואליציונית והצביעה נגד הצעת תנועת החרות להביע אי אמון בממשלה. ההצעה נפלה ברוב של 63 קולות של כל סיעות הקואליציה וכן מק"י והסיעות החרדיות ובהימנעות סיעת הציונים הכלליים, כנגד 11 קולות סיעת חרות.
הוויכוח שקדם להצבעה עורר מחדש מחלוקות אישיות ואידיאלוגיות. בעל ההצעה מנחם בגין הגדיר את הנסיגה כ"בשורת איוב" וקרא לעברו של ראש הממשלה דוד בן-גוריון: "בשם אלוהים – לך!", רמז לקריאתו של לאופולד אמרי לעבר ראש הממשלה הפייסן נוויל צ'מברלין בפרלמנט הבריטי במאי 1940. בן-גוריון השיב כי הוא מסרב להתווכח "עם האומה ועם אלוהים", שבשמם לדבריו התיימר בגין לדבר וכינה את בגין בתואר "מפקד תנועת החרות".
ב-15 בינואר יצאו כוחות צה"ל מאל עריש. הרמטכ"ל רב-אלוף משה דיין היה יחד עם הכוחות המפנים, ולשאלת עיתונאי על הרגשתו, השיב:
צה"ל יצא מאל עריש ובמקומו נכנסו לעיר יחידות יוגוסלביות מכוח החירום של האו"ם.
בו ביום נכנסה יחידה הודית למנזר סנטה קתרינה. כניסתה סמלה יותר מכל את נטישת סיני על ידי ישראל, זאת מאחר שמיד לאחר המלחמה הודגש בעיתונות כי ההר ג'בל מוסא, שהמנזר שוכן על צלעו, הוא הר סיני התנ"כי והודגש שמו בעברית – "הר משה", ורחבעם זאבי כשאליו נילווה אורי דן הניף עליו את דגל ישראל, ורשם שם על קלף:
ב-22 בינואר נסוגו כוחות צה"ל עד הגבול המנדטורי עם מצרים, והמשיכו להחזיק ברצועת עזה והחוף המזרחי של סיני לאורך מפרץ אילת, כולל בשארם א-שייח'.
בראשית חודש פברואר 1957 הגיע הלחץ על ישראל, להשלים את הנסיגה, לשיאו. ב-2 בפברואר הוגשו לעצרת האו"ם שתי הצעות החלטה, האחת להשלים מיד את הנסיגה, בעדה הצביעו 71 מדינות, והשנייה כי בעקבות הנסיגה יבואו מאמצי שלום, בעדה הצביעו 56 מדינות. בעקבות ההחלטה תבע מזכיר האו"ם דאג המרשלד כי ממשלת ישראל תודיע על השלמת הנסיגה עד 7 בפברואר בחצות. הממשלה דחתה את הדרישה.