W lipcu 1867 roku z inicjatywy dyrektora Komisji Spraw Wewnętrznych i Cerkiewnych Królestwa Polskiego, księcia Czerkaskiego, rozpoczęto budowę nowej prawosławnej świątyni. Na miejsce budowy wybrano Pragę szybko rozwijającą się wschodnią dzielnicę miasta. Projekt cerkwi wykonał architekt Nikołaj Syczew, pracami budowlanymi kierował inżynier pułkownik Palicyn. Praska cerkiew była pierwszą warszawską świątynią wybudowaną w rosyjskim stylu. Jej bryłę zwieńczało pięć łukowatych kopuł. Do wnętrza świątyni prowadziły trzy wejścia. Brak było dzwonnicy. Jej funkcje wypełniały cztery małe narożne kopuły. Wszystkie dziesięć dzwonów odlano ze stali we Westfalii. W oknach umieszczono żółte szyby, nadające wnętrzu malowniczy wygląd. Ściany pokryto freskami autorstwa Winogradowa, ikony w trzyrzędowym rzeźbionym i pozłacanym ikonostasie wykonał malarz Wasiljew. Do ogrzewania cerkwi zastosowano centralne ogrzewanie. Zastój w pracach spowodował arcybiskup Joanicjusz, który nie wyraził zgody na zaprojektowane gazowe oświetlenie cerkwi. Ponownie zaprojektowano oświetlenie cerkwi tylko świecami. Wzniesiona kosztem 140 tys. rubli cerkiew mieściła osiemset osób. Aktywnie we wznoszeniu cerkwi wzięła udział cesarzowa Maria Aleksandrowna, która ofiarowała główną ikonę. Na pamiątkę cesarzowej 29 czerwca 1869 roku wyświęcono cerkiew św. Marii Magdaleny. W 1871 roku wybudowano dom parafialny. W 25 rocznicę położenia kamienia węgielnego, w 1892 roku, wyświęcono drugi ołtarz św. Iowa Poczajowskiego. Od 1921 roku, po zamknięciu wszystkich warszawskich świątyń, cerkiew stała się katedralnym soborem Polskiego Autokefalicznego Kościoła Prawosławnego. Nie zważając na to władze polskie kilkakrotnie zamierzały rozebrać cerkiew. W 1928 roku w dolnej części soboru zorganizowano cerkiew Cierpień Chrystusowych, w której umieszczono ocalone mozaiki z soboru na Placu Saskim. Cerkiew w 1944 roku mocno ucierpiała na skutek działań wojennych. Niemniej po II wojnie światowej pieczołowicie ją odbudowano. W ostatnich latach sobór poddano gruntownemu remontowi.