Согласно концепции Мао Цзэдуна, революционная война развивается в три этапа: партизанский период, позиционный период, период манёвра. По такой схеме проходила гражданская война в Китае в 1946—1949 годах и война в Индокитае (1946—1954). С этой точки зрения ФНО на протяжении всей Алжирской войны продолжал действовать в рамках первого периода. Партизаны нападали на армейские конвои, небольшие гарнизоны и посты, взрывали мосты, уничтожали линии связи. Велась и «идеологическая» война: детям запрещали посещать французские школы, простых жителей заставляли отказываться от употребления алкоголя и табака, тем самым вынуждая подчиняться нормам шариата, а заодно нанося удар по определённому сектору французской экономики. Подозреваемых в сотрудничестве с французами убивали, порой — самым жестоким образом.
Французы противопоставили партизанскому движению тактику квадрильяжа, широко применявшуюся в первой половине войны. Страна была разделена на районы (квадраты), каждый из которых был закреплён за определённым подразделением, отвечавшим за местную безопасность. В целом во французской армии достаточно чётко выделялись два типа подразделений: элитные силы парашютистов и Иностранного Легиона вели мобильную войну, проводя операции в различных районах, а все остальные подразделения контролировали ситуацию на выделенной им территории. В Алжире впервые в истории войн для переброски подразделений были широко использованы вертолёты; концепция аэромобильности была проанализирована американскими военными и десятилетие спустя нашла применение во Вьетнамской войне. Довольно большой успех был достигнут в завоевании «сердец и умов» алжирцев, чем занимались Специальные административные секции. Их задачей было вступать в контакт с местным населением в отдалённых регионах и по возможности вести борьбу против националистических идей, склоняя крестьян к лояльности Франции. Эти же подразделения занимались вербовкой местных добровольцев в отряды ополчения, так называемые «харки», которые обороняли свои селения от партизан НФО. Французские спецслужбы вели свою тайную войну в Алжире; в ряде случаев им удавалось подбросить противнику дезинформацию о якобы имевшем место предательстве отдельных командиров и активистов движения, тем самым спровоцировав кровавые внутренние «чистки», серьёзно ослабившие ФНО.
Осенью 1956 года, стремясь привлечь к своей борьбе внимание французов и международного сообщества, ФНО развернул кампанию городского терроризма в городе Алжире. Почти ежедневно на городских улицах взрывались бомбы, гибли колоны, а жертвами акций возмездия становились невиновные алжирцы. Кампания была эффективной и вызвала серьёзную озабоченность французского правительства. В январе 1957 года в городе началась крупная забастовка, приуроченная к обсуждению алжирского вопроса в ООН. Это стало началом так называемой «битвы за Алжир»: в город была введена 10-я парашютная дивизия, а её командир генерал Жак Массю получил чрезвычайные полномочия. Парашютисты начали проводить по всему городу облавы и обыски, задерживая всех подозреваемых в сотрудничестве с ФНО. Применение пыток (нередко оканчивавшееся летальным исходом для допрашиваемого) позволило получить информацию о структуре партизанских сил в городе. Были захвачены многие документы, оружие и денежные средства ФНО в Алжире. По оценке советских источников, «Связь военных округов с городом, откуда поступали оружие, снаряжение, медикаменты, деньги, почти полностью прекратилась.… В течение 1957 г. французским властям удалось разгромить основные силы фидаев и в других городах». Оборотной стороной восстановления порядка в Алжире стала негативная реакция французского общества на информацию о широком применении пыток.
1958—1960
В 1958 году во Франции произошли значительные политические события, спровоцированные шедшей уже четвёртый год Алжирской войной. Всё началось с того, что в январе французский патруль на границе с Тунисом попал в засаду ФНО и понёс большие потери. В этом же районе, возле тунисского селения Сакиет-Сиди-Юсеф, в течение месяца были сбиты два и повреждён один самолёт ВВС Франции. Разведка сообщала, что здесь находится большой склад оружия. 8 февраля французская авиация нанесла бомбовый удар по деревне, при этом погибли примерно 70 мирных жителей. Последствием авианалёта стал кризис во франко-тунисских отношениях, вызвавший большой международный резонанс (вопрос о бомбардировке предполагалось обсудить на специальном заседании Совета Безопасности ООН). В связи с этим правительство Франции приняло решение согласиться на предложенные США и Великобританией «добрые услуги» в посредничестве. Премьер-министру Феликсу Гайяру была предложена идея создания в Северной Африке оборонительного пакта с американо-британским участием; когда он озвучил её, это вызвало волну негодования со стороны ряда правых депутатов парламента, считавших согласие на вмешательство третьих стран в североафриканскую политику Франции предательством. В конце концов, 15 апреля кабинет министров был вынужден уйти в отставку. В стране начался политический кризис; кандидатуру нового премьер-министра не могли утвердить несколько недель.
Тем временем колоны в Алжире с раздражением следили за кризисом в метрополии. В начале мая было сообщено об убийстве партизанами трёх пленных французских солдат. 13 мая премьер-министром был назначен Пьер Пфлимлен, который, как предполагалось, мог начать переговоры с ФНО. Это было последней каплей, переполнившей чашу терпения, как колонов, так и ряда французских генералов. Проходившая в тот же день в Алжире демонстрация в память об убитых солдатах переросла в беспорядки. Был сформирован так называемый Комитет общественной безопасности, во главе которого стал генерал Рауль Салан. Комитет потребовал принять новую конституцию Франции и сделать премьер министром Шарля де Голля. Фактически это был путч. Мятежные генералы планировали в случае отказа от выполнения их требований высадить парашютный десант в Париже.
К этому времени де Голль, ставший в годы Второй мировой войны национальным героем Франции, уже некоторое время находился в политической тени. Он не был причастен к решениям правительства по индокитайской и алжирской проблеме и оказался приемлемой фигурой для всех сторон. Ультраправые считали, что де Голль не допустит «сдачи Алжира», все остальные также надеялись, что он сумеет вывести страну из политического кризиса и решить алжирскую проблему достойным образом. Четвёртая республика пала, ей на смену пришла Пятая. 1 июня де Голль вступил на пост премьер-министра. Сразу после этого он совершил поездку в Алжир, где заявил колонам и генералам: «Я понял вас». На самом деле де Голль испытывал пессимизм по поводу судьбы Французского Алжира. Он сознавал, что процесс деколонизации невозможно остановить и что военным путём алжирская проблема не будет решена.
Боевые действия в самом Алжире не прекращались. С 1956 года ФНО получил возможность рекрутировать новых бойцов из числа беженцев в Тунисе и Марокко, и здесь же их тренировать. Через границу партизаны в Алжире получали подкрепления и оружие. Сознавая это, в 1956—1957 годах французские военные построили укреплённые линии, призванные «запечатать» границы. Линии (наибольшую известность получила линия на тунисской границе, прозванная «линией Мориса» по имени тогдашнего министра обороны) представляли собой комбинацию заграждений из колючей проволоки под напряжением, минных полей и электронных сенсоров, позволявших выявить попытку прорыва и своевременно перебросить войска на угрожаемый участок. Всю первую половину 1958 года ФНО пытался прорвать эти линии, но не добился успеха и понёс тяжёлые потери. С января по июль в ходе, возможно, самых ожесточённых сражений всей войны потери партизан, согласно французским данным, составили 23 тыс. человек убитыми и пленными. Для ФНО наступил тяжёлый период.
Дипломатический фронт борьбы за независимость оставался успешным — Алжирская война обсуждалась мировым сообществом и подрывала международный престиж Франции, а в сентябре было провозглашено Временное правительство Алжирской республики, находившееся в Тунисе. Однако во всём остальном ФНО стал терпеть неудачи. Ему не удалось сорвать в Алжире референдум по новой конституции; попытка развернуть террористическую деятельность на территории континентальной Франции была быстро пресечена полицией. Группировки в Тунисе и Марокко продолжали накапливать силы, но не могли прорваться через границу и помочь отрядам в Алжире. В 1958 году французы начали принудительное переселение жителей ряда районов страны в так называемые «лагеря перегруппировки». Жизненные условия в таких лагерях были, как правило, неудовлетворительными, что не прибавило алжирцам симпатий к Франции, однако повстанцы более не могли рекрутировать новобранцев и получать продовольствие в выселенных районах. Осенью де Голль обнародовал пятилетний план экономического развития Алжира («план Константины») и в угоду ультраправым пообещал крупное военное наступление на партизан. Кроме того, он выдвинул инициативу так называемого «мира храбрых», предусматривавшую амнистию для повстанцев, добровольно сложивших оружие. До сих пор обе стороны обычно убивали случайных пленных, и сдаваться у партизан не было особой мотивации, но теперь она появилась, что обеспокоило не только руководство ФНО, но и колонов.
Обещанное де Голлем наступление началось в феврале 1959 года. Им руководил новый командующий войсками в Алжире генерал Морис Шалль, и его план ведения боевых действий получил название «план Шалля». Это была серия операций, продолжавшихся в различных районах до весны 1960 года с целью разгрома основных сил партизан и их базовых лагерей; местные войска блокировали пути вероятного отступления партизан, а высокомобильные подразделения парашютистов и Иностранного Легиона прочёсывали окружённый район. Эффект этих операций был сокрушительным. Уже в марте командование ФНО приказало своим силам рассредоточиться и действовать группами не более отделения—взвода. По советским данным, в 1959 году ФНО потерял убитыми до 50 % командного состава, были выведены из строя командующие всеми военными округами. Согласно французской статистике, с конца 1958 по конец 1959 года противник потерял больше людей, чем за все предыдущие 4 года войны.