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