Миссионерам очень хотелось духовно связать столицу Алжир и лежавший за морем французский город-порт Марсель, в котором на возвышении 150 метров над уровнем моря возводился католический собор Богоматери-охранительницы. Храм должен был смотреть в сторону Алжира.
В 1855 году французы решили построить на средиземноморском берегу Алжира, на скале, на той же высоте над уровнем моря, католический собор. Обоим храмам отводилась роль связующих духовных центров. Об этом писали газеты, говорили в своих проповедях священнослужители. В 1858 году на высокой скале в Алжире приступили к работам. Предстояло вырубить плато, на котором будет возведен фундамент.
Перед французским архитектором Жаном Оженом Фромажо стояла непростая задача - придать архитектурному облику католического собора арабские черты. Архитектор решил построить обычную базилику с основанием в форме латинского креста, поднять над ней круглый купол с крестом, а перед главным входом соорудить две башни-колокольни, которые олицетворяли бы собой минареты.
На освящении закладки первого камня присутствовал французский епископ и алжирский монсиньер Пави. Последний сказал много хороших слов, в которых упомянул о том, что в Африке теперь будут молиться и за христиан, и за мусульман, а Божия Матерь услышит эти молитвы. Эти слова стали дивизом собора и были выгравированы над алтарем.
Строительство заняло 17 лет. Пришлось преодолеть многие трудности с подвозом требуемых материалов, рабочей силы. Собор в Марселе был готов в 1863 году, а алжирский храм в 1872 году. В 1930 году в соборе Африканской Богоматери появился орган. На нем ранее играл знаменитый французский композитор и органист Камиль Сен-Санс, умерший в Алжире в 1921 году. Его прах позднее был перевезен и захоронен во Франции.
