Через несколько недель более 20 000 арабов из разных стран вышли на арену де Ивер в знак солидарности и скорби по погибшим. Первый секретарь префекта полиции Морис Папон (участвовавший в депортации евреев с Вель-д-Ивер) быстро создал особое соединение — lа Brigade des aggressions et violences (BAV, Бригада подавления агрессии и насилия) для решения «алжирской проблемы». Именно тогда колониальная война шагнула на улицы столицы (и тогда же термин «bavure» — «ошибка, путаница» — стал общепринятым отзывом о Бригаде Папона).
Ситуацию усложняла и подпольная война между ФНО и конкурентами-националистами, сражения разыгрывались прямо на улицах Парижа в XIII, XV и XVIII округах. В XIX округе на улицах Пети и Mo между ФНО, ДТДС и НПА не раз случались перестрелки. Морис Папон пользовался услугами информаторов-алжирцев, он создал целую сеть
Пока алжирцы грызлись между собой, полиция была довольна. Всю вторую половину 1950-х в Париже шла подпольная и кровопролитная война между ФНО и конкурентами-националистами. Газета «L’Aurore» писала, что в 1957 году окрестности улицы Готте-де-Ор, прозванной «парижской Мединой», стали запретной зоной для любого европейца и местом, где боевики ФНО и ДТДС средь бела дня ходят с автоматами наперевес. Но страшнее других были улицы северного Парижа, где «полиция не смела появиться»: рю Шарбонье, рю Шартр, улица Мира и рю Стефенсон, лежавшие в двух шагах от станции метрополитена «Барбе».
Французские левые в большинстве своем симпатизировали движению алжирцев, многие считали, что единственным способом их поддержать является активное участие в борьбе. Преподаватель философии и близкий друг Сартра Франсис Жансон создал в Париже организацию по поддержке ФНО, за что в 1960 году был арестован и предан суду. Жан-Поль Сартр ратовал за Алжир, что вылилось в знаменитый, подписанный ведущими интеллектуалами тех лет «Манифест 121». Общество считало, что французы в Алжире ведут себя не лучше, чем нацисты десятью годами ранее во Франции. Когда слухи о творимых французской армией пытках и убийствах стали широко известны и получили подтверждение, даже самые умеренные граждане не могли найти алжирской войне никаких оправданий.
Шарль де Голль вернулся в правительство, когда алжирский кризис перерос в беспорядки, грозившие гражданской войной, и полностью уничтожил всякое уважение к режиму президента Рене Коти. В том обстоятельстве, что де Голля во власть вернул Алжир, есть немалая ирония. Поводом к конфликту в мае 1958 года послужила массовая забастовка и захват резиденции генерал-губернатора в Алжире, провели который офицеры из правых и рядовые из «черноногих», окончательно разуверившиеся в политике Парижа. Де Голль из осторожности держался от «путчистов» на расстоянии, но воспользовался их действиями, чтобы в соответствии с конституцией возглавить правительство и взять ситуацию в свои руки. В 1959 году, к вящему неудовольствию приветствовавших его приход правых, де Голль утверждал, что единственный выход для «великой нации» — дать алжирцам право на самоопределение.
С возвратом де Голля французская власть вернула себе уважение народа, но спокойствия на улицах столицы так и не прибавилось. Военные действия лишь ожесточились, началась «битва за Алжир» — террористическая кампания ФНО 1957 года, сопровождавшаяся взрывами и перестрелками с целью запугать парижан-европейцев. Столичная полиция обрушилась на всех алжирцев без разбора: и тех, кто хоть отдаленно походил на выходцев из северной Африки, и потенциальных террористов. Наконец Морис Папон совершил худшее — установил комендантский час для «французских мусульман североафриканской внешности».
Такая политика привела к катастрофе: 17 октября 1961 года десятки тысяч алжирцев собрались в центре города на демонстрацию с требованиями мира и независимости. Полиция отреагировала жестоко и беспощадно, чем напомнила обществу о депортациях евреев с Вель-д-Ивер: Папон пригнал полицейские фургоны и грузовики, в которые, жестоко избивая, грузили демонстрантов и свозили на стадион де Кубертен, во Дворец спорта и Шато де Венсенн. Перепалка между демонстрантами и полицией на мосту Нейи переросла в настоящее сражение: тяжеловооруженные полицейские отряды напали на толпу, убили двух и ранили множество демонстрантов. После этого полиция начала убивать алжирцев без счета и сбрасывать тела в Сену.