Le général Challe lance le plan du même nom : Plan Challe qui aboutit à une victoire militaire sur le terrain sans que la situation politique ne s’améliore, le fossé se creusant entre les communautés et les critiques internationales continuant. Le FLN constitue une armée des frontières en Tunisie.

► Février 1959 : rapport de Michel Rocard sur les camps de regroupement.

► 29 mars 1959 : mort de Amirouche Aït Hamouda, chef de la wilaya 3, et de Si el haouès, chef de la wilaya 6, lors d’un affrontement avec l’armée française, alors qu’ils se rendaient à Tunis pour y contester le rôle du GPRA.

► Du 27 août au 30 août, voyage du général de Gaulle en Algérie, au cours duquel il évoque la participation des Algériens à leur avenir, sans prononcer le motautodétermination.

► 16 septembre 1959 : le général de Gaulle évoque publiquement une autre voie que la seule victoire militaire, parlant dans son discours de septembre, du « droit des Algériens à l’autodétermination » et proposant trois solutions : sécession, francisation ou association, ce qui va enflammer les milieux Algérie française.
Les Français d’Algérie sont indignés de cette déclaration qu’ils considèrent contraire aux engagements pris à l’issue du 13 mai 1958 et de l’arrivée au pouvoir du général de Gaulle. De nombreux militaires ne comprennent pas qu’une solution autre que française puisse être proposée alors qu’ils se sont battus depuis quatre ans contre le FLN.