La double faillite du gouvernement Guy Mollet ravive l’appétit du Général pour le pouvoir même s’il n’a jamais cessé d’observer la vie politique française et internationale, en Algérie, tout d’abord, où les succès militaires français ne débouchent que sur un durcissement du conflit et son internationalisation. En Égypte, ensuite, où l’intervention conjointe franco-britannique, à la suite de la nationalisation du canal de Suez, le 26 juillet 1956, s’achève par un fiasco. Bien qu’ayant anéanti l’armée égyptienne, avec l’appui israélien, Français et Anglais doivent cesser le feu le 7 novembre sous la double pression des Soviétiques (qui menacent les Européens du feu nucléaire) et des Américains. Le 15 novembre 1956, les contingents de l’Onu débarquent en Égypte alors que les Français, comme leurs alliés anglais, doivent se retirer piteusement à partir du 22 décembre face au diktat américano-soviétique. La France n’a pas été aussi violemment humiliée depuis bien longtemps.
Alors que le départ de Jacques Soustelle, fugace gouverneur général de l’Algérie (depuis février 1955), le 2 février 1956, est salué par des acclamations, la visite du président du Conseil Guy Mollet donne lieu à de violentes manifestations. Elles sont organisées par les nationalistes Pierre Lagaillarde (député) et le cafetier Joseph Ortiz et soutenues par les anciens combattants et les mairies. Bombardé de tomates, Guy Mollet va pourtant changer d’opinion radicalement. Refusant désormais d’abandonner les Européens, il en revient à une politique d’intégration et de maintien de l’ordre. Georges Catroux, ministre résident désigné par Guy Mollet, est remplacé par Robert Lacoste, missionné pour conduire la guerre contre le FLN. Le 12 mars, l’Assemblée nationale vote des pouvoirs spéciaux au gouvernement en Algérie. Guy Mollet décide d’engager le contingent. Au total, appelés et rappelés réservistes passent de cinquante mille à environ quatre cent mille, alors que le service militaire est porté de dix-huit à vingt-sept mois.
Sur le terrain, Robert Lacoste cherche à reprendre le contrôle des villages, en implantant des SAS (Sections administratives spécialisées), et des villes, avec les SAU (Sections administratives urbaines). Puis il engage les militaires à regrouper les populations pour mieux les protéger. Face à la campagne des fellaghas, la création des Caper (Caisses d’accession à la propriété et à l’exploitation rurale) dont l’objectif est la nationalisation des grands domaines européens pour les revendre en parcelles à de petits exploitants agricoles indigènes, s’avère un cuisant échec. L’Assemblée nationale algérienne est dissoute le 12 avril.
Le FLN adopte désormais une stratégie d’élimination de tous ses concurrents nationalistes. Il entend devenir le seul représentant de la révolte. Le 18 mai 1956, à l’issue de l’embuscade de Palestro, il démontre sa volonté d’incarner l’unique force antifrançaise en suppliciant quinze soldats capturés, retrouvés morts dénudés, émasculés et les yeux crevés. Puis s’étant structuré en absorbant l’UDMA de Ferhat Abbas, un parti de notables, il se met en ordre de bataille au congrès de la Soumman. Six wilayas sont instaurées alors que l’ALN est constituée et qu’un organe exécutif de cinq membres, le CCE (Comité d’organisation et d’exécution), voit le jour.
La découverte de pétrole à Hassi Messaoud puis de gaz à Hassi R’Mel, en 1956, donne à ce conflit colonial un enjeu économique majeur.
À la fin septembre et au mois d’octobre 1956, des jeunes femmes algériennes se transforment en porteuses de bombes. Les nombreuses explosions qu’elles provoquent font des dizaines de victimes, en particulier dans les cafés des rues Michelet (Cafeteria) et d’Isly (Milk-Bar), à Alger. La France réagit avec brutalité, commettant un acte de piraterie dans le ciel international. L’avion transportant les dirigeants en exil du FLN (Ben Bella, Aït Ahmed, Khider, Boudiaf et Lacheraf) est intercepté et détourné par les forces aériennes françaises. Faits prisonniers, emmenés en France, ces cinq dirigeants ne seront libérés que lors des accords d’Évian de mars 1962.