3 мая 1945 года, незадолго до окончания Второй мировой войны, Нойштадт-ин-Гольштейн и Нойштадтский залив стали ареной преступлений нацистов и морской катастрофы, произошедшей в результате бомбардировки судов «Cap Arcona» и «Тильбек», на которых находились узников концлагерей.
На двух баржах СС переправило через Балтийское море в Любекский залив узников концлагеря Штуттхоф (около Данцига) — мужчин, женщин и детей разных национальностей, в том числе многих евреев и евреек. Сначала баржи пришвартовались к «Тильбеку», а затем пристали к берегу на пляже возле дома лоцмана между Нойштадтом и Пельцерхакеном. Сотням узников концлагеря удалось выбраться на берег. Там и на баржах многие из них были застрелены солдатами СС и морской пехоты, а также полицейскими, вызванными населением, утром 3 мая, а остальные — по дороге к военно-морским казармам на Виксберге.
Многие из убитых были сначала похоронены в братской могиле недалеко от места высадки барж. Это место захоронения на сегодняшней улице Штуттхофвег с 1946 года стало официальным кладбищем. Туда же британские военные власти перезахоронили вынесенные на берег тела жертв кораблекрушений «Кап Аркона» и «Тильбек», произошедших во второй половине дня 3 мая. В 1947 году там был установлен мемориал, а в 1948 году состоялось официальное открытие кладбища как мемориального.
Параллельно с созданием мемориального кладбища на пляже еврейский комитет лагеря для перемещенных лиц в Нойштадте добивался того, достойно похоронить еврейских погибших, которые до того времени были похоронены в братской могиле у лоцманской станции, в других одиночных и братских могилах на пляже и на кладбище областной больницы, на отдельном кладбище. Уже в августе 1945 года с этой целью велись переговоры с евангелической приходской общиной Нойштадта о покупке части территории кладбища на Грасвеге.
Во второй половине 1946 года были установлены первые надгробные камни. 5 января 1947 года, наконец, состоялось открытие кладбища, о чем в еврейской газете «Unzer Sztyme», издававшейся в лагере для перемещенных лиц в Бельзене, появился подробный репортаж. Согласно этому сообщению, «у лагеря для перемещенных лиц в Нойштадте собрались сотни евреев из Нойштадта и окрестных городов и деревень, а также делегации других национальных комитетов с венками и сформировали траурную процессию. В гнетущей тишине траурная процессия с делегациями во главе прошла через город к месту проведения памятной церемонии на еврейском кладбище». Там выступили раввин Джоэл Халперин и Пол Трепманн из Центрального комитета евреев в британской оккупационной зоне, а также представители города Нойштадт-ин-Холштайн.