Одновременно с 1945 года на другом берегу Средиземного моря зарождалась новая война, которая потрясет Францию до основания. Жизнь французов вскоре будет определять не только Париж, но и Алжир. Но в данный момент мало кого из жителей столицы волновали события, происходящие вдалеке от города. Однако долго не замечать происходящее было невозможно. Очень скоро эхо алжирских событий прокатится по улицам Парижа.
Новая катастрофа разразилась в 1945 году: до Парижа дошли тревожные слухи о пролитой крови на тихом рынке городка Сетиф в Алжире. Поговаривали, что алжирские мусульмане превратили демонстрацию в восстание. Митингующие алжирцы среди флагов стран-победителей Англии, Франции и России несли знамя родного Алжира. Когда полицейские попытались его отобрать, началась стрельба. Вооружившись топорами и ножами, демонстранты напали на европейских поселенцев, на так называемых «pied noirs» («черноногих»). За пять дней боев были убиты более ста европейцев: многим перерезали горло, других изувечили до неузнаваемости. Мужчин кастрировали, женщин наси-ловаловали. Местные религиозные лидеры объявили джихад и провозгласили долгом каждого мусульманина убивать всех неверных.
Неслучайно печально известное восстание началось 8 мая — в День победы, когда нацисты прекратили военные действия в Европе. Понятное дело, в Париже все новости из-за границы растворились в пьяных оргиях, танцах и гуляниях. Ни одна парижская газета не посчитала нужным выслать в Алжир собственного корреспондента. Даже де Голль отмахнулся от этих новостей, посчитав, что Франция имеет дело с «локальным восстанием в Константине, <…> которое прозевал генерал-губернатор Шатено».
Реакция Франции была жестокой — войска за несколько недель уничтожили около 6000 мусульман. Военные показали «крепкую руку» (и выместили злобу за недавние унижения от немецких оккупантов). Каирское радио объявило, что погибли более 45 000 алжирцев, и алжирские националисты поверили в эту статистику. После случая в Сетифе алжирский кризис свелся к отдельным стычкам между французской армией и националистами из Народной партии Алжира (НПА), которая позднее была преобразована во Фронт национального освобождения (ФНО). Вялая реакция властей дала алжирским националистам время спланировать и организовать продолжительную и жестокую войну. Заодно они уладили все внутренние раздоры. В 1954 году ФНО, получавшая деньги от арабского мира, оснащенная новым оружием и марксистско-ленинистской идеологией, взяла ситуацию дома и во Франции в свои руки.
Война в Алжире официально началась в праздник Всех святых, после того как ФНО в ответ на взрывы и памфлеты, подогреваемый радиопередачами из Каира, объявил о своей программе «восстановить государство Алжир, превратить его в независимое, демократическое и с основанное на принципах ислама общество»; причем допустимыми считались любые методы достижения этой высокой цели. Для упрощения операций руководители ФНО разделили Алжир на шесть «вилайя» (арабское слово, обозначающее территорию, находящуюся под правительственным или военным контролем). Другой пункт партийной программы ставил целью донести «войну до Франции» и превратить Париж в «седьмую вилайю».
Возобновление вооруженного противостояния в Алжире сопровождалось массовым бегством мирных граждан в Париж. Иммигранты прибывали не только из Алжира, но и со всего североафриканского побережья. Официальная статистика утверждает, что в период между 1947 и 1953 годом из Алжира в Париж переселилось 740 000 человек. Реальные цифры, скорее всего, были значительно выше.
Изначально беженцы из Северной Африки селились в центре столицы, где в 1920-х и 1930-х годах проживали их земляки: на площади и улице Мобер, в Л’Аль, на окраинах Клиши и Женевилье (где издавна обосновались марокканцы). Поколение предвоенных иммигрантов давно состояло на учете и находилось под особым надзором сил правопорядка. Префект полиции Кьяп в 1925 году даже создал специальное отделение, которое должно было держать североафриканское население Парижа под контролем. Особое полицейское подразделение базировалось в доме № 6 на улице Леконт в XVII округе столицы. После освобождения города от нацистов отряд упразднили — сотрудники, набранные из экс-колонистов, подозревались в связях с гестапо и вишистами.