3 maja 1945 roku, tuż przed końcem II wojny światowej, Neustadt w Holsteinie i zatoka Neustädter Bucht stały się miejscem zbrodni nazistowskich oraz katastrofy morskiej spowodowanej bombardowaniem statków „Cap Arcona” i „Thielbek”, na których znajdowali się więźniowie obozów koncentracyjnych.
Na dwóch barkach SS przetransportowało więźniów obozu koncentracyjnego Stutthof (koło Gdańska) – mężczyzn, kobiety i dzieci różnych narodowości, w tym wielu Żydów i Żydówek – przez Morze Bałtyckie do Zatoki Lubeckiej. Po tym, jak najpierw zacumowano je przy statku „Thielbek”, barki te ostatecznie przybiły do brzegu w pobliżu domu pilotażowego między Neustadt a Pelzerhaken. Setkom więźniów obozu udało się dostać na ląd. Tam oraz na barkach wielu z nich zostało zastrzelonych przez żołnierzy SS i marynarki wojennej oraz policjantów, zaalarmowanych przez ludność, w przedpołudnie 3 maja, a kolejnych w drodze do koszar marynarki wojennej na Wieksbergu.
Wielu z zamordowanych zostało początkowo pochowanych w zbiorowej mogile w pobliżu miejsca wyładunku barek. To miejsce pochówku przy dzisiejszej ulicy Stutthofweg stało się następnie od 1946 roku oficjalnym cmentarzem. Władze wojskowe Wielkiej Brytanii kazały tam również przenieść ciała wyrzucone przez morze po katastrofie statków „Cap Arcona” i „Thielbek”, która miała miejsce po południu 3 maja. W 1947 roku wzniesiono tam pomnik, a w 1948 roku odbyło się oficjalne poświęcenie cmentarza honorowego.
Równolegle z utworzeniem cmentarza honorowego na plaży żydowski komitet obozu dla wysiedleńców w Neustadt zaangażował się w godne pochowanie zmarłych Żydów, którzy do tej pory byli pochowani w zbiorowej mogile przy domu pilota, w innych pojedynczych i zbiorowych grobach na plaży oraz na cmentarzu szpitala krajowego, na własnym cmentarzu. Już w sierpniu 1945 r. rozpoczęły się negocjacje z ewangelicką gminą Neustadt w sprawie zakupu części terenu cmentarza przy Grasweg.
W drugiej połowie 1946 roku postawiono pierwsze nagrobki. 5 stycznia 1947 roku odbyło się w końcu poświęcenie cmentarza, o czym ukazała się szczegółowa relacja w żydowskiej gazecie „Unzer Sztyme”, wydawanej w obozie dla wysiedleńców w Belsen. Zgodnie z tymi informacjami „w obozie dla osób wysiedlonych w Neustadt zgromadziły się setki Żydów z Neustadt oraz okolicznych miast i wsi, a także delegacje innych komitetów narodowych, które przyniosły wieńce i utworzyły kondukt żałobny. W przytłaczającej ciszy kondukt żałobny, z delegacjami na czele, przeszedł przez miasto na uroczystość upamiętniającą na cmentarzu żydowskim”. Wystąpili tam rabin Joel Halperin i Paul Trepmann z Komitetu Centralnego Żydów w strefie okupowanej przez Brytyjczyków, a także przedstawiciele miasta Neustadt w Holsteinie.