V Paříži se usazovali ruští imigranti již od 18. století. V 19. století se počet Rusů v Paříži dále zvyšoval a jejich počet byl kolem tisíce, ať již stále či dočasně bydlících. K modlitbám se zpočátku scházeli na ruském velvyslanectví, které však kapacitou nedostačovalo, proto se věřící rozhodli vybudovat vlastní pravoslavný chrám.
Ruský kaplan Josef Vasiljev přišel s plánem na jeho výstavbu v roce 1847, zahájení stavby však se zpozdilo. Stavbu, ke které dal souhlas císař Napoleon III., se podařilo dokončit roku 1861. Slavnostní vysvěcení se konalo 11. listopadu téhož roku v den svátku sv. Alexandra Něvského, patrona chrámu. Finanční prostředky na tuto stavbu byly sbírány především ve Francii a v Rusku. Na stavbu kostela přispěl i ruský carAlexandr II. sumou 150 000 franků. Dary ovšem přispěli i mnozí katolíci a protestanti.
Chrám je vybudovaný v tzv. novobyzantském architektonickém slohu podle plánů architekta Romana Ivanoviče Kuzmina. Má půdorys řeckého kříže, jehož každé rameno je ukončeno apsidou. Každou apsidu zdobí kupole, a těchto pět kupolí představují Ježíše Krista a čtyři evangelisty. Nejvyšší kupole má výšku 48 m. Interiér chrámu zdobí fresky a ikonostas s ikonami od významných ruských malířů.
