Cmentarz położony przy ulicy Okszowskiej został założony w czerwcu 1941 roku. Do lipca 1944 roku pochowano na nim 60 000 żołnierzy jeńców wojennych. Między kwietniem a lipcem 1944 roku w Stalagu 319, podzielonym na 4 podobozy (A, B, C, D), przetrzymywano około 200 000 jeńców różnych narodowości, w tym jeńców francuskich.
Cmentarz został uporządkowany w 1954 roku, w roku, w którym utworzono 48 mogił zbiorowych. Kolejne etapy prac miały miejsce w 1963 roku: teren cmentarza został powiększony, a liczbę mogił zwiększono do 57. W latach 2004–2012 przeprowadzone badania wykazały, że większość pochowanych tu żołnierzy pochodziła z Armii Czerwonej. W następstwie tych badań zmieniono pochodzącą z 1961 roku inskrypcję o jeńcach wojennych „polskich, radzieckich, jugosłowiańskich, francuskich i włoskich”. Nowa tablica, odsłonięta w maju 2014 roku z okazji 70. rocznicy zamknięcia Stalagu, jest poświęcona „pamięci 60 000 jeńców Stalagu 319 A i 319 C w Chełmie, żołnierzy armii radzieckiej różnych narodowości, maltretowanych i zamordowanych przez Niemców w latach 1941–1944, których prochy tu spoczywają”.