В январе 1958 года начался заключительный этап войны. К этому, времени командование АНО отказалось от действий крупными силами и возвратилось к партизанской тактике борьбы. Было решено сократить число проводимых операций, сделав упор на подготовку личного состава, а активными наступательными действиями лишь поддерживать состояние военного "равновесия". Такая стратегия "изматывания", по мнению руководства ФНО, должна была заставить Францию предоставить Алжиру политическую независимость.

1 июня 1958 года, после смены нескольких правительств к власти пришел генерал Шарль де Голль. Чтобы урегулировать алжирскую проблему, де Голль представил проект новой конституции, по которой Алжир объявлялся равноправным членом франко-африканского сообщества. Однако лидеры ФНО призвали население бойкотировать референдум по новой конституции, мотивируя это тем, что в сложившихся условиях не может быть и речи о свободном волеизъявлении алжирцев.

В июне 1958 года командование АНО отдало приказ о переходе в наступление на всей территории Алжира, с тем чтобы помешать подготовке и проведению референдума.

18(19) сентября 1958 года в Каире было объявлено о создании Алжирской республики и образовании Временного правительства Алжирской республики (ВПАР).

Премьер-министром Временного правительства стал Фархат Аббас

Несмотря на неутихающие боевые действия, французским властям все же удалось провести референдум и получить одобрение новой конституции 96,5% голосов, принявших в нем участие.

После референдума де Голль заявил о своем намерении провести в Алжире широкие социальные и экономические преобразования и полуофициально предложил лидерам ФНО прекратить вооруженную борьбу, пообещав добровольно сложившим оружие прощение. Но, поскольку французское правительство не согласилось признать независимость Алжира, борьба продолжалась.