Руководящий комитет «социальных республиканцев» решил воспользоваться тем, что Шабан-Дельмас занимал пост министра обороны в правительстве Гайяра, и послать в Алжир в качестве официальных представителей этого министерства голлистов Леона Дельбека и Люсьена Нейвирта. Основной целью деятельности посланников должна была стать агитация за возвращение к власти генерала де Голля, а также привлечение на его сторону двух основных оппозиционных правительству сил, отстаивавших лозунг «французский Алжир», — ультраколониалистов и командования армии.
Весной 1958 г. голлистам удалось связаться в Алжире как с лидерами ультраколониалистов, так и с представителями командования французской армии. Дельбек и Нейвирт прямо заявили и тем и другим: «...мы приехали сюда для того, чтобы сказать вам, желающим спасти Алжир, что вы сможете это сделать, только опрокинув систему и заменив республику генералом де Голлем». Однако ни военные, ни «ультра» не спешили связывать себя какими-либо обязательствами по отношению к голлистам. Тем не менее Дельбек и Нейвирт постоянно курсировали между Парижем и Алжиром, расширяли связи в алжирской столице и докладывали о своей деятельности руководству «социальных республиканцев» и лично генералу де Голлю.
Решающие события развернулись в алжирской столице в мае 1958 г. После падения кабинета Гайяра президент республики наметил на пост главы правительства представителя МРП Пьера Пфлимлена. Кандидат в председатели Совета министров выступал за сохранение Алжира под властью Франции, но считал, что нужно прекратить военные действия и начать переговоры с ФНО. Поэтому его кандидатура была встречена крайне неодобрительно среди алжирских «ультра» и командования армии, которые считали, что переговоры с ФНО — это начало капитуляции.
Обсуждение программы и утверждение полномочий Пфлимлена в Национальном собрании состоялось в Париже 13 мая 1958 г. В ответ на это ультраколониалисты подняли в алжирской столице настоящий мятеж. В тот же день к «ультра» примкнули представители французской армии в лице офицеров парашютно-десантной дивизии и ее командира генерала Массю, а также голлисты Дельбек и Нейвирт. Мятежники создали так называемый Комитет общественного спасения Алжира и потребовали создания аналогичного комитета в Париже. Дельбек склонил членов комитета выступить с обращением к де Голлю, что они и сделали. В первом коммюнике мятежников говорилось: «Комитет умоляет генерала де Голля прервать свое молчание и создать правительство общественного спасения, способное сохранить Алжир».
15 мая Дельбеку удалось привлечь на сторону мятежников главнокомандующего французскими войсками в Алжире генерала Салана. Он от своего лица также выступил с призывом к де Голлю. Тогда же и сам де Голль начал борьбу за свое возвращение в политику. Он выпустил декларацию, в которой извещал, что намерен вернуться к власти. Он писал: «Некогда, в тяжелый для нас час, страна доверилась мне, чтобы я повел ее к спасению. Сегодня, когда стране предстоят новые испытания, пусть она знает, что я готов взять на себя власть республики».
Мятежники в Алжире расширяли свою деятельность. Туда прибыли сторонники генерала Жак Сустель, Роже Фрей и др. Им удалось окончательно направить мятеж в голлистское русло. Правительство в Париже практически бездействовало. А де Голль 19 мая уже собрал журналистов на пресс-конференцию.
Прежде всего генерал провозгласил себя сторонником демократии и республики, напомнив, что в послевоенный период, возглавляя Временное правительство, он «восстановил гражданские свободы» и «провел прогрессивные социально-экономические реформы». Относительно положения в Алжире он высказался очень уклончиво, сказав лишь, что в сложившихся кризисных условиях армейское командование, «выполняя свой долг по наведению порядка, поступило правильно». На вопрос, касающийся его возможного прихода к власти, де Голль ответил, что хотел бы получить «чрезвычайные полномочия на формирование своего кабинета». Когда в конце пресс-конференции генерала спросили, не собирается ли он ограничить общественные свободы, он ответил: «Разве я когда-либо это делал? Наоборот, я их восстановил, когда они исчезли. Неужели кто-нибудь думает, что в 67 лет я собираюсь начать карьеру диктатора?»
Тем временем в Алжире ширилось Движение 13 мая. Во многих городах были созданы местные комитеты общественного спасения, во главе которых встали военные. 23 мая был образован объединенный Комитет общественного спасения Алжира и Сахары. По существу, это был комитет, созданный еще 13 мая, но расширенный за счет введения в его состав новых членов. Его основная цель теперь была сформулирована следующим образом: «Обеспечить приход к власти правительства общественного спасения во главе с генералом де Голлем, чтобы провести и защитить коренную реформу институтов Французской Республики».