После выборов 1955 года Бен-Гурион опять стал лидером своей партии и сформировал новое правительство, заняв посты премьер-министра и министра обороны. Проблемы не заставили себя ждать. Когда Бен-Гурион еще формировал кабинет, египтяне подписали в Праге соглашение о поставках огромных партий советского оружия через Чехословакию. Шаткое равновесие на Ближнем Востоке было нарушено. Израиль безуспешно пытался предотвратить сделку по дипломатическим каналам.
Затем президент Насер открыто заявил, что покупка оружия является важным шагом на пути к решающему сражению, цель которого — уничтожить Израиль. Египет и прежде не позволял израильским судам проходить через Суэцкий канал. Теперь же Насер блокировал Тиранский пролив в Красном море, тем самым закрыв доступ к южному израильскому порту Эйлату.
По распоряжению Бен-Гуриона начальник генерального штаба Армии обороны Израиля Моше Даян разработал план, предполагавший удар по Египту, захват южной части Синайского полуострова и освобождение Тиранского пролива. Однако Бен-Гурион решил отложить операцию и попытаться сначала приобрести оружие, соответствующее уровню вооружений Египта.
Переговоры с Соединенными Штатами об американских гарантиях Израилю и о поставках оружия продолжились и в 1956 году, но не дали результата. Великобритания также не захотела помочь. Бо́льшую сговорчивость проявила Франция, вовлеченная в это время в тяжелую войну в Алжире. Шимон Перес, генеральный директор министерства обороны, закрепил дружеские отношения с Францией, в результате чего эта страна стала главным поставщиком вооружений для Израиля в течение целого десятилетия. В апреле 1956 года в Израиль прибыли первые истребители «Мистер-4».
Бен-Гурион сместил Моше Шарета с поста министра иностранных дел и перевел его на работу во Всемирную сионистскую организацию. Министром иностранных дел стала сторонница более активной политики Голда Меир, которой предстояло укрепить и расширить союз с Францией. Французы не только обеспечивали поставки оружия, но и начали склоняться к идее совместных с Израилем действий против Насера, который оказывал поддержку алжирским мятежникам и снабжал их оружием.
Критический момент наступил 26 июля, через два дня после того, как в Израиль прибыл первый транспорт из Франции: Насер национализировал Суэцкий канал, принадлежавший Франции и Великобритании. Эти страны сразу же взялись за разработку военной акции против Египта, чему воспрепятствовали Соединенные Штаты. В сентябре Франция начала активно готовить план военных действий против Насера в сотрудничестве с Израилем.
Бен-Гурион с большой осторожностью отнесся к планам, выдвинутым французами и англичанами, особенно к английской идее относительно «израильского предлога»: имелось в виду, что сперва Израиль нападет на Египет, а уж потом Великобритания и Франция оккупируют зону Суэцкого канала, чтобы развести воюющие стороны. Подлинные намерения англичан вызывали у Бен-Гуриона сомнения. Он не хотел, чтобы эти две державы использовали Израиль в своих интересах. Бен-Гурион предвидел, что если Израиль начнет действовать в одиночку, это вызовет осуждение международного сообщества, и потому стремился к полноправному сотрудничеству. Кроме того, Бен-Гуриона тревожила реакция США и СССР, а также возможность атаки новых египетских бомбардировщиков советского производства на израильские города.
20 октября 1956 года Бен-Гурион вылетел во Францию для тайных переговоров с представителями английского и французского правительств. Он по-прежнему не доверял англичанам. Однако Египет уже образовал объединенное военное командование с Сирией и Иорданией, на границе с Египтом участились террористические нападения на мирных граждан, и Бен-Гурион понимал, что выхода нет — необходимо уничтожить базы террористов, с которых проводятся операции против Израиля. Кроме того, он придавал значение тому факту, что Израиль сумел заключить союз с крупной западной державой — Францией.
Согласно плану, израильские парашютисты должны были овладеть перевалом Митла к западу от Суэцкого канала, затем пересечь границу, напасть на базы террористов в Газе и двигаться на юг, имея задачей освобождение Тиранского пролива. Франция должна была обеспечить воздушное прикрытие израильских городов. Затем Англия и Франция предъявят Израилю и Египту ультиматум с требованием отойти на десять миль к востоку и к западу от канала. Если египтяне ответят отказом, английские и французские войска войдут в зону канала.
В это время Бен-Гуриону было уже семьдесят лет. Напряженность момента стоила ему немалых сил. После заседания кабинета у премьер-министра поднялась температура, ему пришлось лечь в постель. Дома он принял лидеров израильских политических партий и сообщил им о плане действий. Его старый соперник Бегин, глава крупнейшей оппозиционной партии «Херут», выразил Бен-Гуриону полную поддержку.