尽管有审查制度和保密措施，法国在阿尔及利亚“维和”行动使用酷刑的真情还是源源不断地被揭露出来，越来越多地引起法国民众的忧虑，也使他们对法国在那里的使命产生了怀疑。1957年末，一位著名的殖民地事务专家罗伯特·德拉维涅特颇具前瞻性地写道：“最严重的问题不在于残暴行径本身，而在于国家因为这些残暴行径，正在走向自我毁灭。我们在阿尔及利亚所目睹的一切，无异于国家的瓦解；它是威胁法国自身的一块痈疽。”
不过，马絮将军的伞兵部队和情报部门还是有效地捣毁了民阵的行动网络，包括它的炸弹工厂、秘密武器库和战斗小组。袭击活动从1月份112起降到了3月份29起。民阵指挥部幸存下来的成员被迫逃亡到突尼斯寻求避难。6月间，一家“黑脚”频繁光顾的赌场舞厅被炸，袭击活动出现了短暂的回潮。但到了秋天，最后一名炸弹袭击组织者被抓获，所谓的“阿尔及尔战役”最终以法国的胜利而告终，“黑脚”们也很快恢复了正常生活。
年初，法军司令部判断，法国已经最终赢得了战争。城市恐怖袭击活动已经被挫败；农村地区的“安抚”计划正在实施；一批总共可容纳100万农民的安置营正在建设中，民阵在农村地区的依托可望彻底清除。军队还成功地招募了数千名阿尔及利亚当地人充当雇佣军，协同法国军队作战。为防止民阵从突尼斯和摩洛哥的基地渗透，军方沿阿尔及利亚边境全线建起了一个“拦阻坝”系统，包括电网围栏、地雷阵和雷达预警，发挥了显著的功效。
法国之所以要全力保住在阿尔及利亚的殖民统治，还有一个新的、强有力的动机——石油。经过十年的不懈努力，就在战争开始后不久，在撒哈拉沙漠纵深地带的哈西迈斯欧德地区发现了石油。1958年1月，第一桶石油开始流向法国。
与此同时，民阵领导层陷入了严重混乱。被迫撤出阿尔及利亚后，民阵高层在突尼斯进行了重组。打城市战证明是一个灾难性的策略，而在农村地区，又无力与法军抗衡。领导层内部不和、士气低落，加上与另一个民族主义组织阿尔及利亚民族运动发生争斗，民阵受到严重困扰，其生存在很大程度上依赖于突尼斯的支持和保护。可是，即使有布尔吉巴提供总部基地、武器供应渠道，以及民阵部队避难营地和训练设施，民阵游击队想要穿越“拦阻坝”还是极其困难。在“拦阻坝”于1957年建成后的头七个月里，据民阵自己估计，它在“拦阻坝”一带损失人员多达6000人。
在阿尔及利亚，法国军方成功地获得了强势地位，与此同时，在法国本土，政府却陷于四面楚歌。罢工浪潮此起彼伏，经济动荡不安，再加上国际社会对阿尔及利亚冲突的批评，法国一届又一届政府轮番上场，拼命而又徒劳地支撑着第四共和国。1957年5月，居伊·摩勒内阁倒台后，在长达22天时间里，法国没有了政府；随后，在10月和11月间，又有35天时间没有政府。1958年4月，又一届内阁倒台，法国再度处于无政府状态。政府领导层陷于真空状态，国家弥漫着萎靡的气氛，法国在全世界名誉扫地，法国政客的愚蠢行为遭到世人日益强烈的反感。
这种情绪最为强烈的莫过于军方。法国军队在印度支那败在共产党手下，在奠边府遭遇惨败，在世界舆论压力下被迫蒙辱撤出苏伊士。这桩桩充满怨恨的记忆萦绕心头，促使军方下定决心，决不能任由巴黎那些懦弱政客背叛出卖，眼睁睁看着阿尔及利亚的胜利成果从手中溜走。他们确信，阿尔及利亚人的民族斗争就是共产主义不断侵蚀的铁证，而保卫法属阿尔及利亚的战争则是捍卫西方价值观斗争的基本组成部分。因此，他们的使命不只是为了恢复法国的伟大尊严，而且是为了阻止西方的颓势。他们相信，只要直接打击民阵在摩洛哥和突尼斯的目标，就能够完成他们在阿尔及利亚的使命，目前只是因为政客们担心国际社会的反应，束缚了他们的手脚。
令军方更为恼火的是，巴黎有迹象表明，一些显赫政客打算放弃“法国的阿尔及利亚”。4、5月间，巴黎在全力以赴为新内阁寻找一位新总理。这期间，主要候选人皮埃尔·弗林姆兰竟然宣布，一旦获得任命，他打算与民阵开始谈判。对此，驻阿尔及利亚法军总司令拉乌尔·萨朗将军正式提出了抗议。他声称，军队所能接受的惟有叛乱分子被彻底击败。5月9日，在致巴黎的法军总参谋长的一份电报中，他发出军队将干预国家政治的警告：“如果国家的代表们缺乏维护‘法国的阿尔及利亚’的决心，拼死奋战的军人们将付出无谓的牺牲，对此，驻阿尔及利亚的军队将难以认同。”
就在这天晚些时候，一个事件的发生，引发了饱含愤怒、怨怼和怀疑的强烈反应，将法属阿尔及利亚推入一场动乱之中。这天，民阵在突尼斯宣布，作为对法国人处决民阵战士的报复，将处决三名法国士兵，他们都是在四个月前被俘虏的应征青年。
于是，整个军队和“黑脚”居民炸了窝。萨朗宣布，将在5月13日为三名死难士兵举行官方悼念仪式。“黑脚”们的各种组织则准备在同一天举行大规模示威游行。而在5月10日这天，罗伯特·拉科斯特总督意识到自己将被调离，居然悄然离开，回巴黎述职去了。巴黎仍然没有政府，而阿尔及尔也没有了总督。
