Park im. Jana Pawła II (XIV-XX) dawniej zwany Kapitańskim Zaułkiem. W latach 1357-1889 stał tu najstarszy ustecki kościół pw. św. Mikołaja, patrona kupców i żeglarzy, pierwotnie wyświęcony jako katolicki. Był to centralny punkt średniowiecznej osady. Przy kościółku grzebano zmarłych, m.in. ofiary katastrof morskich. Na podstawie zachowanych pieczęci kościelnych przypuszcza się, że z wieży wywieszano światło nawigacyjne dla żeglarzy. Wokół placu domy budowali najbogatsi szyprowie i kapitanowie; stąd nazwa Kapitański Zaułek.

Kościółek przypominał architekturą bliźniaczy, do dziś stojący w pobliskich Zimowiskach. W XVII w. działy się tu cuda: w nocy świece przy ołtarzu zapalały się same. W połowie XIX w. średniowieczny kościółek, obliczony na 200 osób, stał się za mały, by pomieścić wiernych. Dlatego zbudowano nowy przy ul. Wyszyńskiego, a ten rozebrano i na jego miejscu urządzono skwer. W 1995 r. ustawiono tu koło młyńskie, pochodzące prawdopodobnie z wiatraka, który do początków XX w. stał w pobliżu promenady.