Русское присутствие во Франции датируется начиная с XVIII века. В XIX веке около тысячи русских постоянно или временно проживают в Париже. С 1861 года церковь при русском посольстве в Париже находилась в специально нанятом особняке на улице де Берри. Помимо живущих в Париже русских, прихожанами посольской церкви были православные греки, славяне, валахи, арабы — и в праздники храм уже не вмещал всех молящихся. В 1847 году священник русского посольства протоиерей Иосиф Васильев озаботился возведением постоянного храма в Париже.
Французская административная медлительность сдерживали завершение проекта, но Император Наполеон III в конце концов дает своё согласие. В июне 1857 года состоялась аудиенция протоиерея Иосифа Васильева у Императора Александра II, который дал согласие на сбор общественных средств на строительство храма в Париже. Государь пожертвовал от себя и своей супруги 50 тысяч рублей (возместил также перерасход сметы строительства храма в сумме 134 тысяч руб.), столько же — Синод, ещё 50 тысяч рублей отец Иосиф собрал среди купцов на Нижегородской ярмарке, крупные суммы внесли русские парижане, в их числе граф Павел Дмитриевич Киселёв, Посол России во Франции. Из необходимых 260 тысяч рублей серебром собрано было 230 тысяч. На покупку у семьи Аннонсэ участка в 2,3 гектара на улице Круа-дю-Руль, близ парка Монсо, пошло 185 тысяч франков. Проект вызвал большой интерес во Франции. К пожертвованиям на строительство храма присоединились католики и протестанты. Во Франции было собрано свыше 2 млн франков.
19 февраля 1859 года, в день четвёртой годовщины восшествия на престол Императора Александра II, в присутствии официальных лиц России и Франции был заложен первый камень в основание нового храма.
Под наблюдением Штрома и Кузьмина, который трижды надолго приезжал в Париж, здание строил каменных дел мастер Жорж Дена, подрядчиком выступал Альфонс Ардон.
Новый храм был освящён 11 сентября (30 августа) 1861 года викарием Санкт-Петербургской епархии епископом Ревельским Леонтием (Лебединским) (впоследствии митрополит Московский и Коломенский). На торжестве присутствовал весь состав российского посольства во главе с Послом графом Павлом Киселёвым и представители Императора Наполеона III. В крестном ходе иконы несли: граф Николай Муравьёв-Амурский, бывший губернатор Восточной Сибири, князь Алексей Лобанов-Ростовский и граф Иван Толстой, член Государственного совета. Посвящён святому князю Александру Невскому.
В 1876 году на двух колокольнях храма были установлены колокола, отлитые из бронзы Гильдией купцов города Саратова на средства отставного полковника П. Д. Бутурлина.
Храм получил статус кафедрального собора в 1922 году, когда архиепископ Евлогий (Георгиевский) устроил здесь административный центр (кафедру) епархии приходов русских эмигрантов. С февраля 1931 года — в юрисдикции Константинопольского Патриархата.
С 1983 года здание охраняется французским государством как исторический памятник. Начиная с 1996 года, проведены большие реставрационные работы.
В 2011 году при соборе стараниями протоиерея Василия Шевчука была создана молдавская Благовещенская община.
В настоящее время собор относится к Архиепископии западноевропейских приходов русской традиции Русской Православной Церкви. Настоятель – митрополит Дубнинский Иоанн.