איסר הראל תמך גם הוא בהמשך הממשל הצבאי ונימוקיו היו גם מתחום יחסי החוץ של ישראל כמו, התמיכה הגדולה של רוסיה הסובייטית בלאומנות הערבית, והתגברות העיסוק בנושאי הלאומנות הערבית עם עלייתו לשלטון של גמאל עבד אל נאצר במצרים. בנוסף סבר איסר הראל שהממשל משמש כמכשיר יעיל לבלימת הקומוניסטים הערבים ומאפשר גיבוש מדיניות אחידה כלפי המיעוט הערבי, שאחרת תתפצל בין משרדי משלה רבים ותאבד את אחידותה.
בעדויות האזרחים הערבים הופיעה בין השאר עצומה שעליה חתמו כאלף תושבים מהכפרים קלנסווה, אום אל-פחם וטייבה, בה הם קובלים על שלילת חופש התנועה, התערבות בעניינים פנימיים, רדיפות על רקע לאומי שכולם יחד עוזרים לטיפוח יחס האיבה של הערבים כלפי היהודים והמשטר בישראל.
בעיתון "אל-מרצאד" ב-5 ביוני 1958 פרסם תושב טייבה על אודות המסחר שנעשה בהסדרת רישיונות מעבר. גורמים שונים מנצלים את המצב לטובתם ומבקשים תשלומים תמורת השגת רישיון. גם אגודה בשם "איחוד" שהוקמה לשם קירוב לבבות בין האוכלוסייה הערבית ליהודית פנתה לוועדה ובין שאר נימוקיה כנגד הממשל טענה שהוא מהווה גורם אנטי חינוכי לבני הנוער, גורם נזק לביטחון ומהווה ביזיון לדמותה של המדינה.
רוב של שלושה חברים: פנחס רוזן מרדכי בנטוב וישראל בר יהודה הצביע בעד ביטול הממשל, כנגד שניים, בכור-שלום שטרית וקדיש לוז שהתנגדו לביטול. הוועדה המליצה להפסיק את הממשל הצבאי אולם עם זאת המליצה להשאיר על מקומן את תקנות ההגנה משנת 1945.
ייתכן שהרוב בוועדה הושפע גם מדברי יועץ ראש הממשלה לענייני ערבים, שכתב במסמך פנימי מספטמבר 1959 את הדברים הבאים:
הממשלה לא הסכימה עם מסקנתה של ועדה זו ובן-גוריון אף איים להתפטר מתפקידיו, החלטת הכנסת השאירה את המצב על כנו.
הממשל הצבאי בין השנים 1958–1963.
בן-גוריון התנגד כל השנים לביטולו של הממשל הצבאי, אולם בשנות כהונותיו האחרונות, ייתכן שבלחץ ההולך וגובר של ההתנגדויות לממשל, הוא נתן הוראות להקלות בתקנות הממשל הצבאי, ובכך החלו השלבים הראשונים של התהליך הארוך לביטול של הממשל הצבאי.
מספר גורמים הביאו לשינוי באופן חשיבתו של השלטון הישראלי. אחד היו הפקת הלקחים והמסקנות שלאחר סיומה של מלחמת סיני. התברר שיש לקבל את התושבים הערבים בישראל כעובדה קיימת ותושביה אינם מתכוונים כלל לעבור לארצות אחרות, כפי שקיוו השלטונות קודם לכן. מרדכי נמיר שהיה אז יושב ראש ועדת מפא"י לענייני הערבים אמר בישיבת הוועדה: "אני יוצא מתוך הנחה שהערבים שישנם בארץ יישארו – אלא אם תהיה קטסטרופה". שמואל דיבון יועץ ראש הממשלה לענייני ערבים כתב גם הוא במסמך שכותרתו "המלצות לטיפול במיעוט הערבי בישראל":
גורם נוסף, היה הזעזוע שגרם טבח כפר קאסם בדעת הקהל הישראלית, והמשפט שהתקיים אחר כך שבו הועמדו לדין 11 קצינים וחוגרים שהיו מעורבים בטבח. שמונה מהנאשמים הורשעו ונדונו לתקופות מאסר ממושכות שבין 7 עד 17 שנה.
הגורם השלישי היה קשור בשגשוג הכלכלי שהחל בשנת 1958 והיה חסר תקדים אפילו בקנה מידה בין לאומי. צמיחה זו הביאה לצורך ההולך וגובר בידיים עובדות במשק היהודי, ואילץ את השלטון להקל על חופש התנועה של הציבור הערבי, שהיה חלק ניכר מעתודות כוח העבודה. על פי נתוני הלשכה המרכזית לסטטיסטיקה היה מספר המועסקים הערבים בשנת 1959 כ-10,000 ואילו בשנת 1966 עלה מספרם ל-40,000.
ב-5 באוגוסט 1959 החליטה הממשלה על מתן מספר הקלות בחופש התנועה מאזורי הממשל. שאפשרו לערבים לנוע מאזורי הממשל שבהם הם גרים – הגליל, המשולש, הנגב – לתוך הערים היהודיות, אולם לא לתוך אזורי ממשל אחרים. עם זאת, המציאות קבעה עובדות בשטח וחלה תזוזה במספר התושבים הערבים שיצאו ממקומות מגוריהם לעבר היישובים היהודיים. החלה עלייה מומרצת במספרם של הפועלים הערבים במשק היהודי החל משנת 1958, ובאוגוסט 1958 החלו הערבים גם להתקבל כחברים בהסתדרות העובדים.
בפברואר שנת 1960 זכו מתנגדי המאבק הוותיקים במק"י לתמיכה מסוימת בהתנגדותם לממשל, כאשר מפלגות חרות והציונים הכלליים הגישו לכנסת שלוש הצעות לסדר היום כנגד הממשל. אם כי בניגוד למק"י, מפלגת חירות לא דרשה לבטלו כליל אלא רק להחליף את התקנות המנדטוריות בחוקי הגנה ישראליים. הצעות אלו נדחו בקולות הקואליציה של מפא"י מפ"ם ואחדות העבודה.
האירועים שקרו באותו זמן מחוץ למדינת ישראל כמו פירוקה של ברית האיחוד בין סוריה למצרים, קע"ם וההפיכות הרבות בסוריה שבאו לאחר פירוקה של ברית זו, יצרו בדעת הקהל הישראלית הרגשה של ביטחון גדול יותר ופיחות בגודל איומו של העולם הערבי על ישראל. כיוון שקודם לכן בתקופת הברית, היה אזור הגבול עם סוריה מקור לעימותים צבאיים רבים. ב-30 במרץ 1958 התנהלו באזור הכנרת קרבות ארטילריה ושריון בין כוחות סוריים לכוחות ישראליים. וקרבות אלו, והגיעו לשיאם בנובמבר 1958. הפסקתם של עימותים צבאיים אלו הקלו על התחזקותו של מחנה המצדדים בביטול הממשל.
בשנת 1961 נבחרה הכנסת החמישית והורכבה ממשלה חדשה שבה הייתה חברה מפלגת מפד"ל, מפ"ם נשארה מחוץ לממשלה. שוב הוגשו על ידי מפלגות שונות חמש הצעות חוק שדרשו באופן זה או אחר לבטל את הממשל הצבאי. דיונים אלו הגבירו מאוד את המסע הציבורי כנגד הממשל, נערכו עצרות רבות ונכתבו מאמרים רבים בעיתונות בעד וכנגד. בן-גוריון איים בעקבות כל אותן אספות מחאה, שאם הממשל יבוטל הוא יתפטר. כל ההצעות נפלו אולם ברוב דחוק ביותר.
בשנת 1963 נערכה ברחבה שלפני קולנוע מוגרבי בתל אביב, הפגנה רבת משתתפים של קהל מעורב יהודי וערבי אנשי רוח ידועים כמו פרופ' מרטין בובר, פרופ' ישעיהו ליבוביץ, פרופ' אפרים אלימלך אורבך פרופ' דן פטינקין ואחרים. המשתתפים חתמו על פניה ציבורית לביטול הממשל. בשנים 1962 ו-1963 שוב עלו הצעות לביטול הממשל ושוב נדחו.
שלבי ביטול הממשל הצבאי 1963–1966.
ב-6 ביוני שנת 1963 התפטר דוד בן-גוריון ולוי אשכול שהיה שר האוצר מונה לתפקיד ראש הממשלה. ב-21 באוקטובר 1963 הודיע לוי אשכול על הקלה בתקנות הממשל, שהייתה לה השפעה רבה על חיי היום-יום של האוכלוסייה הערבית. על פי הודעתו, כל האוכלוסייה הערבית בגליל ובמשולש, פרט ליחידים המוגדרים כסיכון ביטחוני, תשוחרר מהצו שהיה קיים עד עתה, הדורש לשאת רישיון תנועה אישי. הקלה זו סימנה את התחלת המפנה שיחול מעתה ואילך בעמדת השלטון בדבר ביטול הממשל הצבאי. בנאום בכנסת ארבעה חודשים לאחר מכן, הודיע ראש הממשלה החדש שהוא מתכון להמשיך בהקלות כלפי האוכלוסייה הערבית, אולם אין לו כוונה לבטל כליל את הממשל ותקנותיו. הוא קבע שיש לצמצם עד כמה שאפשר, את המגע הישיר בין אנשי הממשל ובין האוכלוסייה הערבית. מטרתו הייתה על פי הגדרתו, הפיכת הממשל לרואה ואינו נראה.
אחד ממתנגדי הממשל העיקריים, חבר הכנסת אורי אבנרי אמר בתגובה למדיניות זו כי
בו בזמן החליטה ממשלת אשכול על קידום מפעלי התיישבות נרחבים בגליל על מנת להגדיל בו את מספר התושבים היהודים. ברור שפעילות זו לא אפשרה בשלב זה את ביטול הממשל שכן הוא היה נחוץ למימוש תוכניות ההתיישבות. דברים ברוח זו אמר מאיר ארגוב בוועידת מפא"י לענייני ערבים: "לממשל הצבאי יש גם מטרה ציונית. הגליל כולו ערבי ויש מטרה ציונית לפצל אותו ולאכלסו ביהודים.
ב-2 בנובמבר 1965 נערכו בחירות לכנסת השישית ולוי אשכול נבחר לראש ממשלה. בנאומו בכנסת הוא הודיע על כוונתו למצוא דרכים לביטול מנגנון השלטון הצבאי. צירופם של כמה תנאים, אפשרו ללוי אשכול להתנער מדרכו של דוד בן-גוריון בנושא. הוכח שגם לאחר ההקלות בתקנות הממשל האוכלוסייה הערבית ככלל לא מעוניינת לפגוע באוכלוסייה היהודית. סיבה חשובה יותר הייתה השקפתו המדינית השונה של ראש הממשלה אודות תפקיד הממשל בסכסוך הערבי-ישראלי. בניגוד לדוד בן-גוריון, הוא לא התייחס אל הערבים כאל גיס חמישי עתידי וכסיכון ביטחוני מתמשך, אלא ראה בהם תושבים לגיטימיים בארץ, שעל ידי מדיניות נבונה ניתן להפכם למשתפי פעולה עם השלטון היהודי, או לפחות לא עוינים אותו. השינויים הפוליטיים שאירעו בעקבות הקמתה של מפלגת רפ"י שמרבית חבריה היו מתומכי הממשל הצבאי, ופרשו מהממשלה, אפשרה לראש הממשלה אשכול לקבץ רוב המתנגד לממשל. ועוד לפני כן להמשיך במדיניות ההקלות.
חומרתו של הממשל, בפרט בכל הנוגע לחופש תנועה, הלכה ופחתה עם הזמן. אפילו פעיל זכויות האזרח, ולאחר מכן חבר אש"ף, סברי ג'יריס, שהוגלה מהארץ בשל עמדותיו, הודה כי שורת ההקלות שנעשו בממשל הצבאי "נטלו את העוקץ" מהגבלות התנועה.
חיזוק למדיניותו קבל ראש הממשלה מחברי הוועדה המרכזית לביטחון. בראשית קיץ 1965 מונה שמואל טולידנו שהיה בעד ביטול הממשל גם בעבר, לתפקיד יועץ ראש הממשלה לענייני ערבים. ראש האגף הערבי בשב"כ אברהם אחיטוב שמונה גם כן לוועדה היה בעמדה דומה, לדעתם של שניים אלה הצטרף גם ראש הלת"ם במשטרה. המתנגד היחידי בוועדה זו היה מפקד הממשל הצבאי יהושע ורבין שבעמדתו כנגד הביטול, תמך גם הרמטכ"ל יצחק רבין, כך נקבע רוב של שלושה כנגד אחד בהחלטה לביטול הממשל.
ראש הממשלה קבע דרג חדש בממשלו, יועץ ראש ממשלה לענייני ביטחון, ולתפקיד נבחר איסר הראל שבזמן הזה שינה את עמדתו האוהדת לממשל והתנגד להמשך קיומו.
ב-12 בינואר 1966 בעת הצגתה של ממשלתו החדשה, הודיע ראש הממשלה על קבלת המלצות הוועדה ואישורן על ידי היועץ לביטחון, וכי כוונת הממשלה לבטל את מנגנון הממשל תוך השנה הקרובה.