АКП, запрещенная колониальными властями в сентябре 1955, создала в подполье свои боевые группы. По соглашению с руководством ФНО в июле 1956 эти боевые группы влились в состав АНО. Однако АКП, продолжая активно помогать ФНО в военном и политическом отношении, сохраняла свою идеологическую и организационную независимость.
Политическая работа ФНО в массах и эффективность действий АНО усилились после конгресса ФНО в Суммаме (август 1956), на котором был избран высший орган ФНО — Национальный совет алжирской революции (НСАР), определена структура АНО и введены воинские звания, принята первая программа ФНО, предусматривавшая достижение национальной независимости, осуществление аграрной реформы и национализации «крупных средств производства», равноправие алжирцев и европейцев. В 1958 в Танжере и Тунисе состоялись конференции лидеров ФНО Алжира и правящих партий Марокко и Туниса; по решению этих конференций было образовано Временное правительство Алжирской Республики (ВПАР), выступившее за урегулирование алжирского вопроса путём переговоров с французским правительством. ВПАР было признано многими странами Азии и Африки. СССР признал ВПАР де-факто — в октябре 1960 и де-юре — в марте 1962.
Советский Союз постоянно выступал за признание законных требований алжирских патриотов. Вместе со многими социалистическими странами и рядом др. стран (в т. ч. и Африки) СССР требовал в ООН признания права А. на независимость и оказывал дружественному алжирскому народу всестороннюю морально-политическую и материальную помощь, а также помощь оружием.
Тяжёлые потери (1,5 млн. чел. погибших, 2 млн. чел. брошенных в тюрьмы и концлагеря, 9 тыс. сожжённых селений) не сломили алжирцев. Убедившись в безуспешности военного подавления национально-освободительного движения в А., правительство Франции в сентябре 1959 признало право алжирского народа на самоопределение. Однако война продолжалась вследствие давления колониальной реакции в А. и во Франции, организовавшей ультраколониалистские мятежи в А.: европейских «сеньоров», (январь 1960) и профашистской военщины (апрель 1961). Лишь после подавления этих мятежей начались переговоры между правительством Франции и ВПАР. Они закончились подписанием в Эвиане 18 марта 1962 соглашений о прекращении огня, самоопределении А. путём референдума и будущем экономическом и культурном сотрудничестве между А. и Францией (см. Эвианские соглашения). Франция обязывалась в течение 3 лет вывести свои войска из А. (выведены в 1964), в течение 5 лет эвакуировать военные базы в Сахаре (эвакуированы к 1 июля 1967); через 15 лет эвакуировать военно-морскую базу в Мерс-эль-Кебире (в феврале 1968, на 9 лет раньше срока, закончилась эвакуация этой военной базы).
Попытки созданной в 1961 ушедшими в подполье ультраколониалистами военно-фашистской организации ОАС (франц. Organisation armee secrete) сорвать выполнение соглашений путём массового террора в городах успеха не имели. Во время референдума 1 июля 1962, проведённого в соответствии с Эвианскими соглашениями, подавляющее большинство алжирцев высказалось за независимость, которая была немедленно признана правительством Франции.
В июне 1962 в Триполи (Ливия) на сессии НСАР была принята новая программа ФНО. Она предусматривала «сознательное созидание на основе социалистических принципов и народовластия», осуществление аграрной реформы по принципу «земля тем, кто её обрабатывает», национализацию природных ресурсов страны, транспорта и банков, выступала за реализацию социальных требований народных масс: за ограничение местной буржуазии, укрепление уже налаженных связей с социалистическими странами.
В первые месяцы независимости обострились политические разногласия внутри ФНО и произошёл раскол его лидеров на сторонников ВПАР (большая часть его лидеров выступала против Триполийской программы) и сторонников созданного в июле 1962 в г. Тлемсене Политбюро ФНО, стоявшего на позициях продолжения революции. При поддержке основной части АНО во главе с начальником Генштаба АНО полковником Х. Бумедьеном победу одержало Политбюро ФНО. 20 сентября 1962 Политбюро провело выборы в Учредительное собрание, провозгласившее А. Народной Демократической Республикой. Первое правительство республики возглавил член Политбюро ФНО А. Бен Белла. правительство провозгласило своей целью ликвидацию тяжёлого наследия колониализма и многолетней войны (разрухи, голода, безработицы, безвластия и анархии на местах) и строительство независимого А. в соответствии с Триполийской программой.
Правительство республики наладило работу государственного аппарата, в значительной части обновленного или созданного заново путём привлечения кадров ФНО и бывших офицеров АНО. Началось восстановление разрушенных за годы войны селений, зданий и сооружений в городах, возобновилась работа многих предприятий и ферм, брошенных бежавшими из страны европейскими колонистами и капиталистами. По инициативе рабочих, батраков и крестьян на этих предприятиях и фермах были созданы комитеты самоуправления. Их деятельность была узаконена декретами, принятыми в октябре — ноябре 1962. Движение за установление рабочего и крестьянского самоуправления, стихийно начавшееся ещё весной 1962, приобретало всё больший размах. В марте 1963 вся оставленная или не полностью используемая своими хозяевами собственность была передана комитетам самоуправления, которые по закону становились распорядителями предприятий и получили право распределения среди работников избытка прибылей (после выплаты соответствующих отчислений государству). Состав комитетов должен был ежегодно обновляться на одну треть. К осени 1963 после национализации всех принадлежавших европейским колонистам имений и ферм, а также имущества, незаконно приобретённого алжирскими капиталистами, в руках комитетов самоуправления оказалось 2,7 млн. га лучших в А. земель, которые давали 60% всей товарной продукции сельского хозяйства, и свыше 1 тыс. промышленных, торговых и иных предприятий. В октябре 1963 состоялся первый съезд крестьян самоуправляемого сектора, а в марте 1964 — первый съезд рабочих самоуправляемого сектора в промышленности. Ряд бывших лидеров ФНО, связанных с буржуазией, ориентировавшихся на некоторые империалистические державы или просто преследовавших личные цели, возглавили оппозицию курсу правительства и Политбюро ФНО. Эта оппозиция особенно активизировалась после одобрения Учредительным собранием в августе 1963 конституции, провозгласившей целью государства строительство социализма, устанавливавшей президентский режим, однопартийную систему и назначение ФНО кандидатов на все выборные должности в государстве. После одобрения конституции (референдум 8 сентября 1963) и избрания Бен Беллы президентом республики реакция организовала вооруженный мятеж в Кабилии, который с перерывами продолжался вплоть до лета 1965.
Состоявшийся в апреле 1964 съезд партии ФНО (он назван учредительным съездом партии ФНО) принял новый программный документ — Алжирскую хартию, провозгласившую самоуправление основной формой «перерастания национальной народной революции в революцию социалистическую». Эксплуатация наёмного труда была объявлена несовместимой с пребыванием в рядах ФНО. После этого съезда ФНО коммунисты А. вместе с активистами ФНО включились в строительство единой партии. В июне 1964 АКП приняла решение о вступлении её членов в ФНО. (После июня 1965 алжирские коммунисты объявили о создании партии, в 1968 получившей название Партии социалистического авангарда Алжира. )
Затяжка с проведением аграрной реформы, сохранение безработицы в значительных размерах и отсутствие или недостаточность реальных мер, подкреплявших социалистические лозунги Бен Беллы, вызвали недовольство масс. В некоторой степени это недовольство отразил 2-й съезд профсоюзов А. (март 1965), избравший новый состав руководства и уделивший значительное внимание экономическому положению страны. В принятой съездом Хартии профсоюзов были развиты многие положения Алжирской хартии.