Kirik on ehitatud klassitsismijärgses eklektilises laadis, kus on kasutatud vene kirikuarhitektuurielemente.[1] Hoone on ristikujuline paekiviehitis kaheksatahulise haritorniga. Kiriku ehitamiseks hakati annetusi koguma 1845. aastal. Hoone pühitseti 1852. aastal pühale apostlisarnaseleMaarja Magdaleenale; pühitsemistseremoonia peeti 21. juulil 1852. Pühitsejad olid Peterburi metropoliit Nikanor, Moskva metropoliit Filaret, Riia peapiiskop Platon ja õigeusu kiriku Tallinna piiskop Kristofor, Venemaa keiserNikolai I ja keisrinna Marija Aleksandrovna juuresolekul.
Maria-Magdaleena kiriku juurde ehitati 1859. aastal kaks elamut (Linda tänav 2 ja 4), kus on läbi aegade elanud kirikuametit pidanud inimesed.
1993. aastal jagunes kogudus kaheks ning need, kes soovisid jääda Moskva ja kogu Venemaa patriarhi kanoonilisse jurisdiktsiooni, jäid Aleksander Nevski kirikusse.