由于人民的全力支持，民族解放军进行战斗的地区迅速扩大。如果说在初期，武装斗争的进行仅限于阿尔及利亚东部的若干山区，到了1956年初，东面的战斗地区从奥雷斯一直发展到突尼斯边境和北部沿海一带，西面在得雷姆桑同摩洛哥接壤的海岸地区又开辟了新的战场。到1956年底，1957年初，沿海各战斗地区互相连接起来了，并向内地推进，民族解放战争已基本具有全国规模。民族解放军战士这样自豪地说：“白天，我们控制了半个阿尔及利亚，而月亮上升时，整个国家全是我们的世界。”在这种情况下，民族解放阵线将全国划分为六个战区：奥兰、阿尔及尔、卡比利亚、撒哈拉、奥雷斯和君士坦丁，各战区设指挥员负责该区军事、行政事务。各战区下设若干军分区，各军分区下成立若干营、连、排等战斗单位。民族解放军这样严密的组织，使自己能和法国殖民军进行顽强的战斗。
    民族解放军的武器装备不断充实、更新。在战争过程中，他们从无到有办起了几个能生产武器弹药的兵工厂。还从殖民军那里缴获大量武器弹药。据美国《新闻周刊》的一篇通讯报道，民族解放军使用的武器中“有10％到25％是从法国人那里缴获来的。”⑩有时甚至可以向法国军官购买武器，因为有的法国军官贪钱从军械库里偷武器来卖给他们。他们还从国外获得物资，军火等援助。阿尔及利亚军民就是这样武装起来，并且越战越强的。
    民族解放军的战术也有很大提高。他们采用游击战术来消耗，打击敌军，使敌军疲于奔命，被动挨打。法国奉行强硬政策的驻阿总督拉戈斯特也对民族解放军的英勇善战感到“头痛。”法国殖民军不得不改变战争初期的“全面围剿”，“全面扫荡”为“重点围剿”、“重点扫荡”的方针，继而又被迫采取所谓“固守要点”、“全面封锁”的措施，以防守主要城镇、交通线、石油产区和东西边境，并封锁阿尔及利亚解放区。1959年1月起，殖民军封锁阿尔及利亚和突尼斯边境的长300公里，宽半公里，并设有电网的“莫里斯防线”，一再被民族解放军突破。1959年夏季，按“夏尔计划”发动的攻势也很快被民族解放军粉碎了。
    为了推进武装斗争的发展，阿尔及利亚全国革命委员1958年9月19 日在开罗举行会议，宣布成立阿尔及利亚共和国，组成以阿巴斯为总理、贝勒卡塞姆和本·贝拉（被关在法国）为副总理的临时政府。临时政府先设在开罗，后设在突尼斯，胜利后才迁回国内。临时政府的成立标志着民族解放战争进入了一个新的阶段。在国内，广大的农村中建立了解放区。他们摧毁了原来殖民者的各种统治机构而建立起革命政府--人民会议。农民分配到了土地，得到革命政权向他们放发的购买农具、种籽的农业货款。年老者、多子女家庭以及革命烈士家属都能得到一定的经济补助。医疗事业和文教事业有了发展。有的解放区还定期出版报纸。解放区人民积极发展生产，巩固后方，涌跃参军，支援前线，随着革命战争的胜利发展，阿尔及利亚解放区也日益巩固和扩大。
    与阿尔及利亚的情况相反，法国被侵阿战争拖得精疲力竭，在各方面都遭受到沉重的打击。首先，在人力、物力、财力上的损失很大。到1960年初，除被歼灭十多万殖民军外，法国被拖在阿尔及利亚战场上的兵力达六十万人，还消耗了大量军火、物资。1955年至1959年法军费支出高达三万五千亿法郎，法国的财政极端困难，其次，侵略阿尔及利亚的不义之战，遭到世界舆论的强烈谴责和国内人民的坚决抵制，法国国际地位一落千丈，法国政府处于空前孤立和不稳的境地。第三，被长期的战争严重削弱了的法国不得不依靠美援过日子。美国一方面以轰炸机、炸弹、卡宾枪等武器和美元支持法国进行殖民战争，镇压阿尔及利亚人民的反抗；另一方面又不愿法国取胜，而是让它陷于战争泥淖而不能自拔，以便乘机渗入法国的势力范围。第四，法国殖民战争的失败，也加深了法统治集团内部的矛盾。代表法国新兴石油工业和金融垄断资本利益的集团为进一步掠夺阿尔及利亚的石油、天然气和其他矿产资源，要求尽快结束战争。代表大殖民庄园主利益的极端殖民主义者集团则强烈反对。1958年6月上台的戴高乐政府主要代表前一部分人的利益，急于在加强武装镇压的同时，争取可以保证法国利益的政治解决。加之，五十年代末六十年代初，非洲殖民地国家的独立运动蓬勃发展，法国金融资本感到要继续维持住旧的殖民统治地位很困难了。就在这种形势下，奉行独立自主政策的戴高乐政府不得不采取具体步骤同阿尔及利亚进行谈判。
    阿尔及利亚民族解放军有物质上和道义上的能力来继续进行武装斗争，直到取得民族独立。但是阿尔及利亚政府仍积极争取和平谈判，以停止流血冲突。临时政府成立后的第二天，副总理兼国防部长贝勒卡塞姆就在突尼斯的《愿望报》上发表声明说：“（阿尔及利亚共和国）政府的第一个步骤是要求法国政府开始谈判。如果法国还是顽固不化，我们就要继续进行政治斗争和军事斗争。我们不是为战争而战争，而是为了独立和和平，为了阿尔及利亚人民的幸福和繁荣。”（11）阿尔及利亚采取了在坚持武装斗争的情况下，同法国政府进行谈判的方针。
    1958年10月，戴高乐抛出发展经济的《君士坦丁计划》来欺骗阿尔及利亚人民，而不提如何结束殖民制度。它理所当然地为临时政府拒绝了。当第十四届联大将要讨论阿尔及利亚问题时，戴高乐于1959年9月16 日发表一个给予阿尔及利亚人民“自决权”的声明。法国虽然在原则上承认了阿尔及利亚的自决权，但又规定在停火四年内举行“公民投票”，由阿人民选择下列三者之一：分离（独立），与法国完全一体化（法国化），或与法国保持紧密合作的内部自治。所谓自决还不包括阿领土撒哈拉在内。（12）这实际上是继续保持对阿尔及利亚的统治。即使如此，当临时政府于同年11月20日宣布本·贝拉等五人为谈判代表时，法政府马上就关闭了谈判的大门。戴高乐说，他希望到法国会谈的代表是“那些仍在战斗的，而不是那些丧失战斗力的人。”