Le général Salan, nommé commandant en chef interarmées en décembre 1956, releva le défi. Tirant les leçons de la défaite d'Indochine (où il avait commandé en chef de 1952 à 1953), il tenta de mettre en échec les recettes de la «guerre subversive» ou «guerre révolutionnaire», dont s'inspiraient les révolutionnaires algériens. Il commença par réorganiser la hiérarchie militaire en la calquant strictement sur la hiérarchie administrative, pour renforcer leur unité d'action. Le général Massu reçut délégation des pouvoirs de police dans le département d'Alger. De janvier à octobre 1957, le général Massu et sa 10e division parachutiste gagnèrent la «bataille d'Alger», par des moyens qui firent scandale en métropole mais qui firent école dans le reste de l'armée : renseignements par tous les moyens (y compris la torture), retournement et manipulation de ralliés clandestins, encadrement et contrôle de la population. La grève fut brisée, le CCE dut fuir Alger et se réfugier à l'extérieur après la capture de l'un de ses membres : les réseaux politico-administratifs et militaires de la zone autonome d'Alger furent entièrement démantelés. Dans les campagnes, le regroupement des populations évacuées des «zones interdites» et l'action des Sections administratives spécialisées (SAS) gênèrent le recrutement, le ravitaillement et les liaisons du FLN-ALN. Le recrutement de «harkis» et d'autres supplétifs parmi les paysans réfractaires à l'autorité des chefs insurgés et parmi les anciens «rebelles» ralliés, facilita l'action des forces d'intervention. Malgré l'augmentation sensible de ses pertes, l'ALN se renforça grâce aux armes et aux renforts qu'elle recevait du Maroc et surtout de Tunisie, où elle envoyait ses recrues s'entraîner et s'armer. Pour isoler l'intérieur de l'extérieur, le ministre de la Défense André Morice (membre du gouvernement Bourgès-Maunoury de juin à septembre 1957) décida de construire en arrière des frontières des réseaux de barbelés électrifiés et minés (appelés «barrages» ou «ligne Morice»), prolongés dans les zones désertiques par des batteries de canons à tir automatiques déclenché par radar. Ces obstacles n'étaient pas infranchissables, mais la coupure du réseau électrique signalait tout passage aux troupes d'intervention. Au début de 1958, le commandement français estimait que la guerre était virtuellement gagnée, et le ministre résidant Robert Lacoste répétait que la victoire irait à celui qui tiendrait «le dernier quart d'heure». Mais le CCE du FLN, installé à l'extérieur, espérait encore gagner en combinant une offensive de ses troupes de Tunisie et du Maroc, et une pression diplomatique de ces deux pays sur les Etats-Unis et à l'ONU, de façon à internationaliser le conflit par un «Dien Bien Phu» algérien. En janvier 1958, les forces militaires de l'ALN atteignirent 60 000 combattants, dont 10 000 à l'extérieur selon les services de renseignement français (90 000 et 15 ou 20 000 selon l'historien et témoin algérien Mohammed Teguia). De février à mai 1958, organisées en bataillons lourdement chargés d'armes, les troupes basées en Tunisie multiplièrent les harcèlements et les tentatives de franchissement de la ligne Morice. Ces harcèlements provoquèrent le bombardement par l'aviation française du village tunisien de Sakiet Sidi Youcef (69 morts), qui poussa la Tunisie à porter plainte contre la France à l'ONU. L'acceptation des «bons offices» anglo-américains par le gouvernement de Félix Gaillard entraîna son renversement, le 15 avril, et une crise ministérielle qui devint une crise de régime. Pendant ce temps, la bataille des frontières tourna au désastre pour l'ALN, surtout à la frontière tunisienne : la seule bataille de Souk Ahras (28 avril-3 mai 1958) lui fit perdre 620 hommes (tués, blessés, prisonniers) et dissipa le rêve d'un «Dien Bien Phu» algérien. L'armée au pouvoir ? La désignation comme président du Conseil de Pierre Pflimlin, partisan de renouer les négociations avec le FLN en vue d'un cessez-le-feu, décida les chefs militaires à sortir de leur réserve politique. Le 9 mai, le général Salan et ses principaux subordonnés mirent en garde le président de la République contre la «réaction de désespoir» de l'armée devant une politique d'abandon. Le 13, la foule algéroise ayant pris le gouvernement général pour réclamer un gouvernement de «salut public», le général Massu accepta de présider un «Comité de salut public» et réclama un gouvernement présidé par le général de Gaulle. Le général Salan, investi des pleins pouvoirs civils et militaires par Félix Gaillard et par Pierre Pflimlin lui-même, laissa les militaires s'engager dans les CSP, et franchit le Rubicon en criant «Vive de Gaulle» le 15 mai. Il prépara une intervention militaire conjointe des troupes d'Algérie, du Sud-Ouest et d'Allemagne pour imposer au Parlement le retour du général : le plan «Résurrection», que celui-ci décommanda par sa déclaration du 27 mai 1958. Revenu au pouvoir, le 1er juin sans intervention directe de l'armée, de Gaulle félicita Massu d'avoir «canalisé le torrent pour en capter l'énergie» et confirma les pleins pouvoirs du général Salan en le nommant Délégué général du gouvernement. Comme ils le faisaient depuis le 13 mai, les chefs militaires continuèrent d'assumer les fonctions civiles de préfets et de sous-préfets, d'animer les Comités de salut public réunissant Européens et musulmans, d'organiser de spectaculaires manifestations de fraternisation franco-musulmanes, et de faire campagne pour le OUI au référendum du 28 septembre 1958, qu'ils présentèrent comme un OUI à l'intégration de l'Algérie dans la France. Pourtant, de Gaulle fit rapidement savoir qu'il ne laisserait pas l'armée lui dicter sa politique algérienne, et que son rôle était de créer les conditions d'une solution politique en combattant les «rebelles» sur le terrain. Au contraire, selon les officiers qui prétendaient avoir tiré les leçons de la guerre «subversive» d'Indochine, la population était le véritable enjeu de la guerre et le facteur essentiel de la victoire musulmane. L'armée était donc dans son rôle en opposant son «action psychologique» et sa propagande à celles du FLN. Au lendemain du référendum, de Gaulle décida de renvoyer les militaires à leurs tâches guerrières. Le 9 octobre 1958, il ordonna au général Salan de leur faire quitter les Comités de salut public, et de leur faire garantir la liberté d'expression de toutes les tendances sans prendre parti. Il déplaça de nombreux officiers qui avaient participé au 13 mai. Puis il sépara de nouveau les responsabilités civiles et militaires, à tous les niveau en remplaçant le général Salan par deux hommes : le Délégué général du gouvernement Paul Delouvrier, et le général Challe, commandant en chef interarmées.
