Осенью 1956 года войска АНОА перешли к активным наступательным действиям. К этому времени они насчитывали 30 тысяч человек, не считая "мусебили". За пределами Алжира располагались резервы – около 30 тысяч человек в Тунисе и примерно 20 тысяч человек в Марокко [20].
В январе – феврале 1957 года войсками АЗА численностью около 4500 человек была проведена "битва за город Алжир". По мнению руководителей ФНО, эта операция должна была привлечь внимание мировой общественности к борьбе алжирского народа, а также вызвать массовый приток в АНОА местного населения.
Для борьбы с АЗА в городе Алжир французское командование привлекло войска численностью до 80 тысяч человек, ядро которых составляла 10-я воздушно-десантная дивизия. Командованию этих сил были предоставлены чрезвычайные полномочия для борьбы с повстанцами в городе и прилегающих районах. Была разработана специальная тактика действий. Город был обнесен проволочными заграждениями, разбит на секторы, участки, кварталы, а последние – на группы домов. Был введен комендантский час. В секторах находились военные посты и мобильный резерв сил до роты. Чтобы лишить повстанцев продовольствия, был заклеймен весь скот, введена карточная система на покупку продуктов питания.
Активные действия французских властей, проведение периодических "зачисток" города, эффективная работа внешней (агентурной) и внутренней (сыскной) разведок позволили предотвратить вооруженное выступление жителей города Алжира и фактически обезглавить этот округ. Так, например, с 20 января по 8 февраля 1957 года было арестовано и убито более 250 командиров и фидаев и около 500 активистов ПАО [21]. В результате этих мер вся система АЗА, АНОА и ПАО в столице была дезорганизована. Связь военных округов с городом Алжир, откуда до этого поступало оружие, снаряжение, медикаменты, была потеряна, а военный центр, находившийся в столице, не мог координировать действия.
Одновременно с разгромом структур повстанцев в столице французскими войсками был проведен ряд успешных операций в округах. При этом вместо "выборочных действий" против отдельных отрядов и округов АНОА была применена "тактика квадратов", или "тактика домино". Она сводилась к полному очищению от отрядов АНОА выбранного района силами крупных войсковых соединений. Затем войска перебрасывались в соседний район и после его "умиротворения" приступали к аналогичным действиям в следующем районе и т. д.
В январе 1958 года начался заключительный этап войны. К этому, времени командование АНО отказалось от действий крупными силами и возвратилось к партизанской тактике борьбы. Было решено сократить число проводимых операций, сделав упор на подготовку личного состава, а активными наступательными действиями лишь поддерживать состояние военного "равновесия". Такая стратегия "изматывания", по мнению руководства ФНО, должна была заставить Францию предоставить Алжиру политическую независимость.
1 июня 1958 года, после смены нескольких правительств к власти пришел генерал Шарль де Голль. Чтобы урегулировать алжирскую проблему, де Голль представил проект новой конституции, по которой Алжир объявлялся равноправным членом франко-африканского сообщества. Однако лидеры ФНО призвали население бойкотировать референдум по новой конституции, мотивируя это тем, что в сложившихся условиях не может быть и речи о свободном волеизъявлении алжирцев.
В июне 1958 года командование АНО отдало приказ о переходе в наступление на всей территории Алжира, с тем чтобы помешать подготовке и проведению референдума.
18(19) сентября 1958 года в Каире было объявлено о создании Алжирской республики и образовании Временного правительства Алжирской республики (ВПАР).
Премьер-министром Временного правительства стал Фархат Аббас [22], заместителем премьера – Керим Белькасем. Последний являлся также председателем созданного в январе 1960 года военного комитета, который руководил ведением боевых действий в Алжире. Алжирская Республика была признана рядом стран, в том числе КНР и всеми арабскими государствами. В октябре 1960 года Временное правительство было признано Советским Союзом [23].
Несмотря на неутихающие боевые действия, французским властям все же удалось провести референдум и получить одобрение новой конституции 96,5% голосов, принявших в нем участие.
После референдума де Голль заявил о своем намерении провести в Алжире широкие социальные и экономические преобразования и полуофициально предложил лидерам ФНО прекратить вооруженную борьбу, пообещав добровольно сложившим оружие прощение. Но, поскольку французское правительство не согласилось признать независимость Алжира, борьба продолжалась.
К концу 1958 года французское командование разработало так называемый "план Шаля" (по фамилии главнокомандующего французскими войсками), которым предусматривался разгром основных сил АНО, захват их баз и районов дислокации, уничтожение сети ПАО и полувоенных формирований путем общего наступления на марокканской границе до Туниса [24]. В феврале 1959 года французские войска перешли в наступление, ведя его с запада на восток, от марокканской до тунисской границы, и нанося последовательные удары по округам АНО. К этому времени в стране были сосредоточены значительные военные силы, достигавшие вместе с вспомогательными частями, набранными в Алжире, 800 тысяч человек. В боях были задействованы 250 вертолетов, 1400 самолетов, тысячи орудий, минометов [25].
К концу 1959 года французским войскам удалось нанести повстанцам значительный урон и вынудить их отойти из ряда районов. Потери повстанцев с октября 1958 года по ноябрь 1959 года только убитыми составили 68 тысяч человек. В боях погибло до 50% командного состава, были выведены из строя или убиты все командующие округами. Всего же, по некоторым оценкам, АНО за пять лет боев потеряла 145 тысяч человек и к 1959 году насчитывала не более 46 тысяч бойцов с 44 тысячами единиц оружия, включая 850 единиц тяжелого вооружения (орудий, минометов) [26]. К сентябрю 1960 года, по заявлению французского командования, численность активно действующих повстанцев сократилась до 22 тысяч человек, включая 8 тысяч бойцов в регулярных частях Армии национального освобождения [27]. Французский полковник Ж. Руа, побывавший в это время в Алжире, так описывает состояние боевых частей повстанцев:
"С чисто военной точки зрения можно было действительно утверждать, что ФНО разбит. Его последние отряды по сто человек забились в непроходимые скалистые массивы, где были окружены со всех сторон. В других местах положение было примерно такое же, как в Тудже: местные феллахи скрываются в маки, а разбитые отряды, распавшиеся на маленькие группы по десятку человек, каждую ночь меняют свои убежища. Единственная цель их выступлений – поддерживать тревожное положение в стране. Отряды, которые называют армией ФНО, сгруппировались в зонах, примыкающих к алжирской границе, в Тунисе и Марокко. Как могут эти отряды сражаться или заниматься боевой подготовкой? Ночью они пробираются к полосе заграждений и нападают на сторожевые посты и прочесывающие дороги бронемашины. Попытки пересечь заграждения почти всегда обречены на провал; только одиночки могут надеяться, что, растворившись во мраке, им удастся подорвать сеть высокого напряжения, а затем успеть пробраться сквозь минные поля, избежав сосредоточенного огня и ловушек. Организованные отряды гибнут, им не удается пройти незамеченными, и их уничтожают один за другим.
Южнее пройти столь же трудно – там полоса заграждений тянется на сотни километров. Авиация непрерывно наблюдает за территорией в глубине пустынь, где скопления войск, орудий и военного снаряжения неизбежно подвергнутся полному уничтожению. Флот днем и ночью сторожит подступы с моря. Военные действия ФНО все больше сужаются, и французская армия утверждает, что вскоре она их окончательно подавит" [28].
В сложившейся ситуации основная часть АНО стала все больше перемещаться за границы Алжира, отступая на территорию Туниса и Марокко. Так возникли "внешняя" и "внутренняя" АНО. Первая из них усиливалась, получая деньги и вооружение из арабских и других стран (в частности из СССР и Китая), превращаясь не столько в военный, сколько в политический фактор. Вторая же слабела и постепенно выбивалась в неравной борьбе [29].
Одновременно для гражданского населения, с целью изолировать его от повстанцев и тем самым лишить их помощи, французскими властями были созданы "центры перегруппирования". Они представляли собой обширные территории, огражденные колючей проволокой и находящиеся под охраной войск. К сентябрю 1958 года французские власти переместили в "лагеря перегруппировки" 535 тысяч алжирцев [30], а к 1961 году около 2 млн. человек.
