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