Зверства повстанцев изменили отношение к ним со стороны французских военнослужащих, а рост насилия со стороны армии привёл к тому, что партизанские отряды стали пополняться ещё большими темпами. Кроме того, алжирские повстанцы стали получать материальную помощь и поддержку от стран коммунистического блока и арабских государств.
Во Франции события в Филиппвилле привели к смене правительства во главе с премьер-министром Ги Молле. Его политика в отношении Алжира заключалась в том, чтобы сначала выиграть войну, а затем проводить реформы. Меры по увеличению армейского контингента в Алжире вывели войну на общенациональный уровень — численность французских войск в стране возросла с 50 000 человек в 1954 до более 400 000 человек в 1958 году. Сначала контингент пополнялся за счёт ветеранов, которые возвращались из Индокитая. Позднее Алжир стал местом дислокации одного из самых боеспособных французских подразделений — Иностранного легиона. В первые годы войны солдаты французской армии были плохо подготовлены к африканским условиям и не имели опыта ведения антипартизанской борьбы. Основным подходом к борьбе с повстанцами стал «квадрильяжный» метод, согласно которому страна делилась на семьдесят пять секторов. В каждом из них находились гарнизоны, проводилось патрулирование и было налажено сотрудничество с САС (Специальной Административной Секцией) — особой организацией, выступавшей посредником между администрацией и местным населением при проведении военных операций, а также оказывавшей населению социальную помощь.
Важнейшим местом борьбы за независимость стала алжирская столица. Одному из лидеров ФНО Ясефу Саади было поручено начать в городе безжалостный террор с целью дискредитации французского правления, и вскоре Алжир погрузился в хаос с непрекращающимися взрывами и повсеместными убийствами. Террор со стороны повстанцев вызвал ответные действия французов — так называемый ратоннаж (избиение арабов). Известно, что во время боёв за Алжир без вести пропали около 3000 мусульман. Наведением порядка в столице руководили генерал Массю и майор Оссаресс, которые ввели комендантский час и оградили мусульманское население города колючей проволокой. В военном отношении ФНО потерпел поражение — погромы и взрывы в столице прекратились, а Ясеф Саади попал в плен. В самой же Франции бои за алжирскую столицу подняли волну критики в адрес армейского руководства, которое, в свою очередь, испытывало отвращение и ненависть к правительству Четвёртой Республики.
Французский парад в Алжире
Теперь большинство боевиков ФНО оказалось за пределами Алжира (многие нашли укрытие в соседних Тунисе и Марокко), и французские власти сосредоточили свои усилия на изоляции страны, перехватывая корабли и перекрывая воздушные трассы. Помимо этого, на тунисской границе была возведена знаменитая «линия Мориса» — восьмифутовая ограда из колючей проволоки под напряжением в 5000 вольт, минные поля и наблюдательные вышки. Все эти усилия заставили повстанцев ощутить тяжелейшую нехватку оружия и боеприпасов, ставя под вопрос само существование партизанских отрядов.
Однако в это время политическая обстановка в метрополии стала меняться. Непопулярность войны, экономические и социальные затруднения снизили уровень поддержки правительства во Франции, в то время как в Алжире любые планы по смене курса воспринимались черноногими как предательство. 13 мая 1958 года они захватили столицу колонии и провозгласили собственное правительство чрезвычайного положения. Командование армейского контингента поддержало это самопровозглашённое правительство, и Франция была на грани революции, когда в игру вступил Шарль де Голль, ставший премьер-министром. В свою очередь, вожди ФНО объявили о создании Временного революционного правительства Республики Алжир, и эта идея была немедленно поддержана арабскими странами.
Придя к власти, де Голль назначил командующим войсками в Алжире генерала Мориса Шалля, который сразу начал широкомасштабные рейды по поиску партизан. Его «Операция Оранье», начатая элитными частями парашютистов, за которыми следовали механизированные колонны, объединила действия наземных и авиационных частей. Так, вертолёты H-21, прозванные «летучими бананами», за пять минут могли высадить два батальона десантников. Кроме того, для штурмовки наземных целей были переоборудованы триста учебно-тренировочных самолётов. Механизированные колонны блокировали партизан, после чего штурмовики наносили по ним ракетно-бомбовые удары. По словам генерала Шалля, в ходе операции, продолжавшейся два месяца, французам удалось разгромить половину повстанческих отрядов.