Erygowany na zlecenie władz austriackich 31 sierpnia 1802 r. na gruntach szpitala unickiego. Decyzja wynikała z zaleceń higienicznych, przewidujących likwidację dotychczasowych cmentarzy przykościelnych i przeniesienie miejsca pochówków poza granice miasta.

Początkowo cmentarz obejmował przestrzeń, której centralnym punktem była istniejąca do dzisiaj Kaplica Bielskich, powstała zresztą na początku XIX w. jako jeden z pierwszych obiektów cmentarnych. Fundatorem kaplicy był właściciel majątku Uher Ignacy Bielski. Obecnie ta klasycystyczna budowla pełni rolę mauzoleum żołnierzy i ofiar II wojny światowej. Pierwotny cmentarz podzielny był na część katolicką i unicką. Po likwidacji kościoła greckokatolickiego, miejsce unitów zajęli prawosławni. W 1887 r. zakupiono od Józefa Skibińskiego i Karola Radziszewskiego grunt, którego centralnym punktem jest obecnie Kaplica Zajdlerów. Fundatorem obiektu był znany chełmski notariusz Władysław Zajdler. We wzniesionej w 1908 r. w stylu neogotyckim kaplicy miejsce spoczynku znalazł między innymi syn fundatora, noszący również imię Władysław, nauczyciel gimnazjalny i działacz społeczny (pełnił funkcję burmistrza i prezesa rady miejskiej w Chełmie).

Obok dwóch kaplic na cmentarzu parafialnym znajduje się szereg cennych nagrobków, z których najstarsze pochodzą z pierwszej połowy XIX w. Kryją prochy właścicieli ziemskich z okolic Chełma, księży, przemysłowców, żołnierzy oraz miejscowej inteligencji. Szczególnie cenne zostały poddane w ostatnich latach konserwacji z inicjatywy Towarzystwa Opieki nad Zabytkami, które corocznie organizuje kwesty w tym celu. Jeden z najstarszych zachowanych nagrobków pochodzi z 1832 r. i kryje prochy Sebastiana Czaplica. Inne XIX-wieczne pomniki należą do: płk. Tadeusza Zawistowskiego (1855), prałata Antoniego Hryniewieckiego (1855), Karoliny z Zawadzkich Lechnickiej (1880).

Szczególną uwagę zwraca wyniosły kamienny krzyż z wykutym na nim herbem Trzaska, stojący na grobie Henryki z Górskich Niemirowskiej, dziedziczki Nowosiółek (1841). Obok znajduje się mogiła powstańców 1863 r., kryjąca prawdopodobnie prochy poległych w bitwie stoczonej 5 VIII 1863 r. pod Depułtyczami. W centralnej części cmentarza znajduje się duża kwatera polskich żołnierzy poległych w latach 1919-20. Wśród nagrobków z okresu II wojny światowej uwagę zwraca mogiła por. Zbigniewa Adama Twardego pseudonim "Trzask", cichociemnego i dowódcy batalionu 27 Wołyńskiej Dywizji AK.