Haapsalu kaks vanemat teadaolevat kalmistut asusid Piiskopilinnusest idas: Krahviaia Jaani tänava poolses osas ning Jaani kiriku ümbruses. Mõlema surnuaia hauatähised, aga ka kalmud on tänaseks täielikult hävinud. Lisaks kalmistutele maeti keskajal ka Toomkiriku ja Jaani kiriku põrandate alla.
1773. aastal kinkis Uuemõisa mõisaproua Barbara von Richter Haapsalu luterlikule kogudusele tüki maad kalmistu rajamiseks. Kingitud maatükk asus tolleaegsest Haapsalu linna hoonestusest eemal, Uuemõisale kuulunud põllul, Tallinna ja Pärnusse suunduvate postmaanteede lõikumiskohast lääne pool. Kalmistu pühitseti 6. augustil 1773.
1863. aastal võeti kalmistuna kasutusele vana surnuaia ja Posti tänava vaheline ala. 1897. a valmis kalmistu läänepoolses servas väike õigeusukirik. Surnuaia ja linna vahelised mõisa põllud jaotati kruntideks ja hoonestati 19. - 20. sajandi vahetusel. Linnast kalmistule viiv tee (tänane Kalevi tn) kandis Jeruusalemma tänava nime.