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