W 1309 r. pojawiły się najwcześniejsze wzmianki o kościele na płytach nagrobnych, które później zaginęły. W 1315 założono cmentarz po północnej stronie kościoła. Miasto było wówczas jeszcze nieufortyfikowane, stąd w portalach kościoła i otworach strzelniczych w murze pojawiły się ciężkie kraty, aby chronić ewentualnych uciekinierów przed atakiem z zewnątrz. Kiedy w XIV w. miasto opasano murami obronnymi, funkcja obronna kościoła św. Mikołaja straciła na znaczeniu. Zaczął on być typowym, średniowiecznym kościołem parafialnym. Niektóre fragmenty kościoła z najwcześniejszego okresu przetrwały do naszych czasów. Około 1350 r. zbudowano kaplice św. Jerzego i św. Mateusza.
W latach 1405–1420 wzniesiono nowe, trójnawowe prezbiterium z poligonalnym obejściem, nową, dwuprzęsłową zakrystię, nawę środkową podwyższono, przepruwając ją zarazem oknami nad nawami bocznymi. Sklepieniom wewnątrz nadano formę krzyżowo-żebrową. Dach został pokryty czerwoną dachówką. Kościół św. Mikołaja stał się bazyliką, a wygląd, jaki wtedy otrzymał, przetrwał zasadniczo do czasów współczesnych.
W 1481 r. w kościele pojawił się nowy ołtarz główny, zamówiony wcześniej w warsztacie Hermena Rode w Lubece. W 1482 r. kościół otrzymał pierwsze małe organy, zastąpione w 1489 nowymi, skonstruowanymi przez Hermana Stüve z Wismaru.