Esimene õigeusu kirik ehitati Haapsallu 1756. a., mis pühitseti Pühale Kolmainule. 1830 aa. see kirik oli kadunud.
1845. a. 22. juulil pühitseti uue kiriku nurgakivi. Uus kirik ehitati aastatel 1845–1852, seega tunduvalt varem kui ehitati valdav osa õigeusu kirikuid Eestimaal (19. saj. viimastel kümnenditel, s. h. ka kolm kirikut Hiiumaal). Ehituse aegluse Haapsalus tingis rahaliste vahendite nappus. Alustati vabatahtlike annetuste põhjal, kuid peale seinte püstitamist jäi ehitus mitmeks aastaks seisma ning lõpetati aastatel 1850-1852, kui saadi vajalik raha riigi poolt. Kirik pühitseti sisse 21. juulil 1852. aastal apostlisamase Maarja Magdaleena auks ja asub Promenaadi lähistel Rüütli tänaval.
19. sajandi lõpupoolel kujunes Haapsalu tuntud suvituslinnaks. Suvitamas ja puhkamas käisid siin isegi tsaariperekonna liikmed. Kuna väga palju rahvast oli Venemaa erinevatest kubermangudest, oli kogudusekirik, eriti suviti, rahvast puupüsti täis. 1878. aastal asutati koguduse Hoolekogu. Ta ülesandeks oli kiriku korrashoid ja vaeste koguduseliikmete toetamine.
1895. aasta 5.-l veebruaril toimus koguduse hoolekogu koosolek, kus otsustati moodustada kaks komisjoni. Esimene komisjon pidi tegelema kalmistu aia, väravate ja kabeli ehitamisega. Teine komisjon loodi selleks, et korraldada Nikolai kogudusekooli juures rahvale loenguid.
22. mail samal aastal lõpetati kalmistumüür ja väravad. Müür surnuaia ümber ehitati paekivist, kogupikkusega üle 200 meetri (100 саженей, 1 сажень= 2,1336 m.) ja kõrgusega u 1,5 meetrit (5 футов, 1= 304,8mm). Müüri nelja nurka ehitati väikesed tornikesed tahutud kivist, mis kaeti plekiga ja ilustati rauast ristidega. Surnuaia peasissekäigu kohale ehitati kolme võlvkaarega suured väravad. Keskmine võlv on umbes 6 meetri kõrgune ning külgvõlvid pisut madalamad. Väravad ehitati Büsantsi stiilis tahunud kivist ja tellistest ning pealt kaeti plekiga. Keskmise võlvi kohal, mis on oma ülaosas nii surnuaia kui ka tänava poolt kaunistatud ikoonidega süvendites (praegu pole), kõrgub kullatud rist. Uus müür ja väravad läksid Koguduse Hoolekogule maksma 606 rubla Ja 66 kopikat. Ehistust juhtis spetsiaalselt selleks loodud komisjon, kuhu kuulusid Hoolekogu järgmised liikmed : A.K.Nejelov, A.F.Schmidt ja A.F.Makarov.
Koguduse Hoolekogu otsustas, et lisaks kirikule oleks kogudusel vaja ka kalmistul asuvat kabelit. Selle põhjuseks toodi nii religioossed kui ka puht praktilised kaalustlused. Koguduse Hoolekogu mainis oma raportis 2.12.1895. a.
Riia ja Miitavi piiskop Arsenili, kelle valitsemise alla kuulusid ka õigeusu kogudused Eesti-ja Liivimaa kubermangudes, tihti erinevat vajadust paigutada kirst koos lahkunuga mitte kirikusse ega elumajja vaid kabelisse.
Sel eesmärgil ostutati püstitada surnuaiale kabel Neeva Aleksandri auks, imperaator Aleksander 3 mälestuseks. Hoolekogu töötas välja ehituse projekti, võttes aluseks sarnaste kabelite tüüpprojekti. Kabeli ligikaudseks maksumuseks planeeriti 2000 rubla. Piiskopi positiivse otsuse ja õnnistuse puhul planeeriti eeltööd teostada 1895/1896 aasta talveperioodil. Kabeli ehitamisega planeeriti alustada 1896 aasta ehitushooajal.
Komisjon, kes tegeles kalmistuaia ja väravate ehitamisega, asus 1896. aastal ka kabelit ehitama. Püha Vaimu päeval– 13. mail, peale Liturgiat kirikus, toimus ristikäik surnuaiale kabeli nurgakivi panekuks. Diakon luges ette teksti, mis oli kirjutatud tahvlikesele, mis müüriti seina sisse. Seejärel asetasid kohalik preester N. Leisman ja hoolekogu liikmed altariseina süvendisse hõbemündid ja tahvlikese ning müürisid selle koha tellistega kinni.
Kõige lõpuks teeniti surnuaial ühine hingepalvus ning ristikäiguga suunduti tagasi kirikusse.
24. aprillil 1897. aastal pöördus kohalik preester Karp Tiisik taas palvekirjaga Riia piiskop Arseni poole, andes edasi Hoolekogu soovi õnnistuse saamiseks algselt planeeritud kabeli asemele kiriku ehitamiseks. Lisaks algselt mainitud põhjustele ,mis seotud matmistega, toodi välja vajadus kasutada suviti kalmistukirikut eestikeelsete jumalateenistuste läbiviimise paigana. Kirik plaaniti valmis saada 1897. a. juuli alguseks ning Hoolekogu pöördus piiskopi poole ettepanekuga, et viimane ise leiaks võimaluse kiriku sissepühitsemiseks. Samuti avaldati soovi, et koguduse eelmine preester Nikolai Leisman, kelle Haapsalus teenimise ajal alustati kiriku ehitamisega ja kes vahepeal oli üle viidud Riia Katedraali, osaleks samuti kiriku pühitsemisega seotud pidustustel.
Kirik ehitati valmis üle aastaga. Aktiivselt osalesid kiriku ehitamisel I. I. Glazunov, kes annestas raha ning varustas kiriku väga väärtuslike teenistusriistade ning kirikukelladega, aga samuti A. L.Veksin, kes tegi suured annestused ikonostaasi ehituseks ning ise jälgis selle valmimist. Ikonostaasi joonised tegi arhitekt, akadeemik Vassili Vassili pg. Saub koguduse hoolekogu jaoks tasuta. 1897.aasta 5 juulil teenisid kolm preestrit vastvalminud kirikus Koguöise teenistuse. Teenistust alustas kohalik preester ja Haapsalu praost Peeter Sõrkovski, kellele teenisid kaasa Riia linna praost preester Nikolai Leisman ja Emmaste preester Joann Teppo. Litaaniaks ja Hommikuteenistusel kiituslaulu laulmiseks tulid välja ka ülempreestrid Rozdestvenski ja Speranski. Pühapäeva, 6.juuli hommikul ,teenis kohalik preester väikese veepühitsuse kell 8.30.Kell 9 toimus kiriku enese pühitsemise, mille sooritas ülempreester Rozdestvenski nelja preestri kaasteenimisel. Teenistuse lõpus ütles üpr. Rozdestvenski, et kirik on ehitatud eestlaste jaoks ning pr. Nikolai Leisman pööras tähelepanu asjaolule, et algselt kavandatud kabeli asemel sai valmis kena kirik. Peale jumalateenistuse lõppu kutsuti kõik külalised lõunale, mis oli korraldatud võõrastemajas S-Peterburg. Lõunasöögi lõpus koostasid kiriku pühitsemisel osalenud preestrid telegrammi Riia ja Miitavi ülempiiskop Arsenile, edasi saatmiseks imperaator Nikolai 2-le, milles teatasid Haapsalus imperaator Aleksandr 3 mälestuseks ehitanud ja seepärast Neeva Aleksandri auks nimetatud kiriku pühitsemisest. See telegramm esitati imperaatorile, kes omalt poolt kirtutas telegrammile resolutsiooni: Palume tänada, millest Pühima Sinodi oberprokurori abi Vladimir Sablev teatas Riia ülempiiskopile.
Kirik, sellisel kujul nagu ta valmis, et rahuldanud siiski paljude ilumeelt. Ta oli madalavõitu, puudu oli kellatorn. 1898. aasta 29-30 augustil, peale teenistust kalmistukirikust seoses Neeva püha Aleksandri mälestuspäevaga, tegi arhitekt A. F. Krassovski esimese annestuse kellatorni ehituseks kalmistukiriku läänepoolsesse otsa, kirjutades annestuslehele 300 rubla. Sama aasta 18. oktoobril saadi Riia Vaimulikust Konsistooriumist ukaas, millega kalmistukiriku jaoks määrati eraldi kirikuvanem, kelleks sai Haapsalu maakonna ülem N. N. Gresistsev.
1899. aastal jätkus kellatorni ehitamiseks valmistumine. Arhitekt-akadeemik A. F. Krassovvski lubas omalt poolt koostada kellatorni projekti ning võtta enda peale ka ehitustööde juhatamine. Koguduse Hoolekogu, arvestades kiriku ehitamist toetanud isikute soovi,pöördus 24.08.1899. a. taas kohaliku preestri Aleksandr Bezanitski läbi Riia ülempiiskop Agafangeli poole. Koguduse Hoolekogu esimees Nikolai Gresistsev ja Hoolekogu auliige Aleksei Veksin, kuid sel korral ka erilise tähelepanuga asjasse suhtuv akadeemik arhitekt Aleksander Krassovski kogusid kiriku ümberehituseks üle 800 rubla. Krassovski kui akadeemia arhitekt koostas tulevase kiriku plaani, võttis enese peale kiriku ümberehituse juhatamise ning kõike seda tasuta. Kõik vajaminev ehitusmaterjal oli möödunud talve jooksul juba muretsetud. Altariosa oli plaanis jätta muutmata kujul, ümber ehitada taheti vaid kiriku keskosa ning juurde ehitada eeskoda koos kellatorniga ning kuppel. Piiskop andis küsimuse otsustamiseks Riia Vaimulikule konsistooriumile, kes andis vastava loa ümberehituseks 3.09.1899. a.
24.08.1901. a. teatad endine Haapsalu preester ja Läänemaa praost, ülempreester Nikolai Leisman piiskop Agafangelile kiriku lõplikust valmimisest, tuues eriti esile neid ,kes kõige rohkem selle nimel vaeva olid näinud. Kiriku lõplikuks maksumuseks kujunes üle 6000 rubla. Kõige suuremat tänu vääris seejuures Aleksei Veksin, käis kes eraldas ehitustöödeks üle 2000 rubla rahas ning peale selle osales isiklikult tööde juhatamisel ning käis mitmel korral ka ehituse asjus Peterburis. Peterburist tõi ta omal kujul 1900.a. suvel kohale meistrid, kes lõpetasid kiriku viimistlustööd ja siseseinte maalimise. Teise hoolsa abilisena on mainitud arhitekt Aleksandr Krassovskit, kes koostas ümberehituse plaani, juhendas isiklikult ehitustöid ning lisaks annestas ka üle 2000 rubla raha. Lisaks mainiti veel Paraskeva Lesnikovat, Peterburis elavaid Iljanja Nadezda Glazunovi, kes ühiselt varustasid kiriku jumalateenistusnõude, ristide, kirikulippude ja muuga. Lisaks eelpoolmainitule olid suured teened ka Haapsalu politseiülemal Nikolai Gresistsevil, kes annestas mitusada rubla raha ning lisaks otsis annetajaid selle püha ettevõtmise jaoks.
Nagu selgub Aleksei Veksini kirjutas piiskop Agafangelile, toimus uue kiriku pühitsemine tagasihoidlikult 15.07.1901.a.
Enne seda oli kirik täielikult üle värvitud nii väljast kui seest.
Kalmistul asuv kirik jälgi esialgu külmaks suvekirikuks, kuna ahjusid kirikus polnud. Peale sõda, 
1940-te lõpus, kui kirikus teenis preester Vjatseslav Jakobs (hiljem – Tallinna ja kogu Eesti metropoliit Kornelius), ehitati Neeva Aleksandri kirikusse ahi ja korsten. Sellest ajast alates kasutas kogudus kirikut talvekirikuna, kuna teda oli palju kergem kütta kui suurt kirikut Promenaadil.
1962. aastal keelati kogudustel omada abikirikuid ning sel põhjusel oli kogudus sunnitud loobuma kalmistukirikust. Sisustus viidi osaliselt Kiviõlisse, mingid ikoonid ja kirikuriistad on sattunud Läänemaa muuseumi, mingi osa sisustusest, tundub, on lihtsalt hävinud. Kirik ise aga jäi tühjalt ja kasutult seisma.
1964. aastal otsustati aga, et Promenaadil asuv Maarja Magdaleena kirik sobiks linnale sissevõimlaks.
Kogudus sai loa üle kolida tühjalt seisnud Neeva Aleksandri kirikusse kesklinna kalmistul. Kiiruga tehti sisseremont ja sellest ajast alates toimuvadki regulaarsed jumalateenistused kalmistukirikus.
Sellest ajast on koguduses säilitanud topeltnime — Maarja Magdaleena — Aleksander Nevski kogudus.
1993. a. koguduse osa liitus Konstantinoopoli patriarhaadi. Neile tagastati Maria-Magdaleena kirik 1994. a. Tänase päeva seisuga kasutab Aleksander Nevski kirikut Moskva Patriarhaadi Eesti Õigeusu Kiriku Haapsalu Maarja Magdaleena(Neeva Aleksandri) kogudus.
2001. aastal viidi läbi pühakoja altari kapitaalremont ning pärast selle valmimist, 4. augustil 2001 a., viis läbi Tallinna ja kogu Eesti metropoliit Kornelius Suure Kirikuõnnistamise.
Praegu jumalateenistused toimuvad:
Õhtuteenistus — laupäevati kell 17:00
Liturgia — pühapäeviti kell 9:00
Teenistus toimub eesti ja kiriku-slaavi keeles.
