В качестве эксперимента в мае 1956 г. в Оране была сформирована 77-я бомбардировочная эскадрилья ЕВ 77 на шести MD-311. Поскольку эти машины можно было назвать бомбардировщиками лишь условно, результаты боевой работы части оказались скромными, в сентябре ее расформировали. Командование ВВС настаивало на создании в Алжире бомбардировочных частей, вооруженных Douglas В-26 Invader, которые хорошо зарекомендовали себя в Индокитае. В конце концов такое решение было принято.
В октябре 1955 г. в составе GOM 86 появилась 3-я АЭ, с февраля 1956 г. выросшая в отдельную группу GSRA 76. Она располагала 20 Ju 52, выпускаемых во Франции под наименованием ААС-1 Toucan. «Юнкерсы» выполняли патрульные и разведывательные полеты, наносили бомбовые удары. Правда, после того, как в октябре 1956 г. одна бомба взорвалась на борту и погубила самолет с экипажем, от выполнения ударных задач на ААС-1 французы отказались. В июле появилась еще одна эскадрилья с 10 «Юнкерсами», вскоре выросшая в группу ESRA 78. Получила развитие и транспортная авиация: в распоряжение командования в Алжире в январе 1956 г. были переданы десять Nord 2501 Noratlas, а также сформирована новая авиагруппа GT 3/62 Sahara на С-47. Учебный эскадрон ЕЕОС 1/17 полностью переключился на ведение боевой работы, и 1 апреля 1956 г. его переформировали в полноценную боевую авиачасть – 20-ю истребительную эскадру ЕС 20 с двумя эскадрильями по 18 самолетов.
Авиация ВМС также расширяла участие в боях. В первую очередь, это относится к переведенной в апреле из Индокитая флотилии 28F с шестью четырехмоторными патрульными бомбардировщиками PBY-4 Privateer и к «Корсарам» 14-й флотилии (14F). С 10-го апреля «Прайветиры» приступили к патрульным полетам над морем, налетав к концу месяца 350 ч. Однако изношенность самолетов существенно сократила их боевой потенциал. Боевая нагрузка иногда ограничивалась всего четырьмя 125-кг ОФАБ, с которыми бомбардировщики могли подниматься лишь на 3000 м. Для облегчения машин приходилось демонтировать верхние турели с двумя 12,7-мм пулеметами. На основе опыта, полученного вместе с вертолетчиками п-ка Креспэна, флот сформировал 31-ю флотилию (31F), вооруженную недавно закупленными «Летающими бананами» Н-21С. В середине года вертолеты этого типа получили и армейцы.
Все прибывавшие силы без промедления включались в боевую работу. Так, по данным разведки, 14 января в 30 км к югу от г. Бари- ка должна была состояться встреча командиров повстанческих отрядов. На операцию ушли 2 вертолета: один флотский, другой из 57-й группы. Они высадили отряд коммандос, который неожиданно напал на партизан и разгромил их, пленив шестерых человек.
В тот же день в районе тунисской границы совершал патрульный полет «Юнкере». На обратном пути у одного из оазисов он был обстрелян с земли и получил несколько пробоин. Следующим утром он вновь был над оазисом. Около 12.30 там же появилось звено Р-47 л-та Кастеллано, которому требовалось точное целеуказание, ибо к оазису весьма близко подошла своя пехота. За это взялся экипаж Ju 52. По его команде «Тандерболты» спикировали на место сосредоточения муджахидов и сбросили 48 10-кг бомб. Затем они с полчаса ходили над оазисом, поливая его пулеметным огнем. Примерно 20 человек пытались уйти, но Кастеллано их настиг и перестрелял. По окончании этой бойни пехотинцы насчитали 48 убитых и подобрали 35 винтовок. Когда летчик совершал посадку, оказалось, что тормоза истребителя не работают, и Р-47 выкатился за полосу. Покинув кабину, лейтенант насчитал в своем самолете более 200 пробоин!
22 января прошла удачная операция с участием вертолетов. Используя данные разведки о размещении двух рот бойцов АНО, командир 3-го колониального парашютного полка п/п-к Бижар решил атаковать их при помощи вертолетов. Для этого были выделены четыре Н-19 из ЕНМ 2/57. Рано утром «вертушки» начали переброску десантников. На ничего не подозревавших муджахидов с неба внезапно обрушились солдаты и моментально открыли огонь. Они уничтожили 43 партизана, пленили 96 и захватили 112 единиц оружия. Сами потерь не понесли.