Округа, зоны, районы и секторы имели политико-административные органы (ПАО) ФНО, которые действовали либо легально (в районах, освобожденных АНОА), либо в подполье. ПАО в каждом освобожденном административном районе располагали отрядами самообороны, которые служили резервом и выполняли задачи по разведке, охранению и т. д.

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

К концу 1956 года на территории Алжира, а также за его пределами – в Марокко и Тунисе, добившихся к этому времени политической независимости, были созданы учебные лагеря и центры. Здесь же располагались базы снабжения оружием.

Рассчитывая, что боевые операции АНОА послужат сигналом к массовым выступлениям всех алжирцев, военное руководство ФНО отказалось от тактики партизанской войны и перешло к войне обычной. Однако крупные группы (батальон-полк) были менее подвижными, чем мелкие группы (взвод-рота), легко обнаруживались наземной и авиационной разведкой французов и часто подвергались уничтожению.