Kościół został wzniesiony naprzeciwko grodu, na wzgórzu znajdującym się lewym brzegu Słupi. Pierwsza informacja w dokumentach o kościele, pojawia się w 1269 roku i dotyczy właściwie kapelana kościoła, Hermana, którego wspomina Mściwój II książę Pomorza Gdańskiego, w swoim dokumencie adresowanym do zakonu cystersów w Bukowie. Imię kapelana Hermana, znane jest już historykom w 1240 roku, kiedy Herman otrzymał od Świętopełka II wieś Ryczewo, dziś będące słupską dzielnicą. Należy także, wspomnieć o przywileju z 1276 roku, w którym książę Mściwój II daruje młyn znajdujący się obok kościoła św. Mikołaja sołtysowi niemieckiej gminy. Kościół był drewnianą świątynią, gdyż taka zabudowa sakralna była na Pomorzu w tym czasie budowana. Zbudowany został najpewniej przez księcia Świętopełka II, gdyż w tym czasie książę ten panował na słupskiej ziemi. A sama świątynia miała status kościoła prywatnego.

Uposażenie kościoła, było odmienne od wcześniej powstałego kościoła św. Piotra i kaplicy grodowej NMP, leżących w prawobrzeżnej części Słupska, które otrzymywały dziesięcinę z określonych wsi. Kościół św. Mikołaja otrzymywał część dochodów z przyległych pól, młynów, łąk oraz pastwisk. Rodzaj uposażenia oraz imię patrona, które otrzymał wskazuje na to, że świątynia znajdowała się w środowisku kupiecko-rzemieślniczym. Koło kościelnego wzgórza, w kierunku południowym znajdowała się pierwsza osada kolonistów niemieckich, przybyłych do Słupska z terenu Lubeki. Koloniści za książęcym zezwoleniem, założyli tu gminę miejską. Ich sołtysem był wspomniany już Henryk de Werciberg. Na prawym, przeciwległym brzegu Słupi znajdowała się osada kaszubska, której kościołem parafialnym był kościół p.w. św. Piotra. Pierwszy rysunek kościoła św. Mikołaja dający graficzne wyobrażenie o budowli, pochodzi z mapy Lubinusa. Możemy go dostrzec w północnej części panoramy miasta, wraz z zabudowaniami klasztoru norbertanek, przylegającymi do kościoła. Należy zwrócić uwagę, na inny (odmienny od obecnego) kształt wieży zakończony stożkowatym hełmem.

Ponieważ kościół św. Mikołaja był prywatnym kościołem księcia gdańskiego Świętopełka II, mieszczanie słupscy przystąpili do budowy własnej świątyni. Miał to być kościół p.w. św. Maurycego, który to wg badań słupskiego historyka, prof. Barbary Popielas-Szultka był protoplastą kościoła Najświętszej Marii Panny. W czasie panowania w Słupsku rycerzy zakonu krzyżackiego w latach 1329÷1332, zmieniono imię patrona z św. Maurycego na zgodne z maryjną tradycją zakonu. W roku 1281 gmina miejska zwróciła kościół św. Mikołaja następcy Świętopełka II - księciu Mściwojowi II. W tym samym roku Mściwój nadał zakonowi premonstratensów z Białoboków nad Regą, którzy zwani są u nas norbertanami (od imienia założyciela zakonu św. Norberta z Xanten), poza szeregiem słupskich wsi, m.in. kościół św. Mikołaja. Darowizny księcia Mściwoja II, doprowadzić miały do zbudowania w Słupsku żeńskiego klasztoru norbertanek. Siostry zakonne przybyły do Słupska w 1284 roku, słupski zakon stanowił filię męskiego zakonu norbertanów z Trzebiatowa. Głównym celem zakonu była praca duszpasterska.

Najstarsza siedziba słupskiego klasztoru, znajdowała się tuż obok kościoła św. Mikołaja. Nie wiemy dzisiaj jak ona wyglądała, ale przypuszczać możemy, że podobnie jak świątynia, była to budowla drewniana kryta słomą. W roku 1311 norbertanki otrzymały zgodę od margrabiów brandenburskich, aby w relokowanym mieście wznieść nowe, murowane budynki. Po dokładnym zbadaniu właściwego fragmentu średniowiecznych murów obronnych słupskiego grodu, wiadomo dzisiaj, że murowany kościół został zbudowany pod koniec XIV wieku lub na początku XV. Zabudowania klasztorne były budowane jednocześnie z wznoszeniem kościoła, który zwrócony był swoja wschodnią ściana szczytową w kierunku Słupi, zaś zachodnim frontem do dzisiejszej ulicy Grodzkiej (Holstentorstrasse). Po północnej stronie kościoła znajdował się klasztor oddzielony od kościelnych murów wąską uliczką, znaną dzisiaj pod nazwą Krętą (Holtentormauerstrasse). Zarówno budynki klasztorne jak i sam kościół, były podpiwniczone oraz zbudowane na kamiennym fundamencie. Budynek klasztorny miał wysokość jednego piętra. Dzisiaj przypuszcza się, że wieża kościelna została dobudowana po pożarze w 1477 roku, gdyż wcześniej zgodnie z regułą zakonną norbertanów, kościół posiadał tylko małą wieżyczkę dla pomieszczenia sygnaturki - niewielkiego dzwonu. W pożarze spłonęły m.in. organy. W roku 1665 wielki pożar miasta po raz wtóry strawił kościół oraz klasztor. W 1679 ukończono odbudowę klasztoru, natomiast wypalony kościół zakryto jedynie dachem, z powodu braku środków finansowych na pozostałe prace. Dopiero w roku 1737 kościół został odbudowany, dzięki staraniom pułkownika Stedinga i poświęcony na kościół garnizonowy.

Kiedy jednak pułkownik w 1740 roku wyruszył na wojnę śląską, nie uszanowano jego wcześniejszych starań i zamieniono zbór ewangelicki na magazyn i wozownię. W roku 1760 za zgodą rady miejskiej, stacjonujące w Słupsku wojska rosyjskie (wojna siedmioletnia) używały kościoła św. Mikołaja jako cerkwi prawosławnej. Później był używany jako magazyn i strażacka remiza, popadając powoli w ruinę. Około 1770 roku rada miejska postanowiła przeznaczyć budynek na potrzeby oświaty i od 1772 roku były kościół służył jako szkoła wraz z internatem dla ubogich uczniów. Podczas remontu zdjęto uszkodzoną kopułę, znajdującą się między czterema sterczynami.

Kolejny raz przebudowano gmach dawnego kościoła w 1819 roku, przystosowując go do potrzeby szkoły elementarnej. W 1834 roku rozpoczęła działalność pierwsza w Słupsku, żeńska szkoła średnia. Od roku 1926, mieściła się w kościele św. Mikołaja szkoła dla dzieci niedorozwiniętych umysłowo (Hilfsschule). Dawny klasztor norbertanek zmienił się na początku XX wieku w fundację panien Froulenstift. Zakon, choć w zmienionej formie, trwał w tym samym miejscu od chwili założenia przez ponad 600 lat. W marcu 1945 roku, w czasie pożaru roznieconego przez czerwonoarmistów na Starym Mieście, kościół św. Mikołaja spłonął całkowicie. Przyległy klasztor zdewastowany i opuszczony, rozebrano w celu pozyskania cegieł. W roku 1961 poznańska Pracownia Konserwacji Zabytków wykonała dokumentację historyczną w celu odbudowy kościoła św. Mikołaja i jego adaptację na potrzeby biblioteki miejskiej. W dniu 10 września 1971 roku dokonano uroczystego otwarcia biblioteki, której nadano imię Marii Dąbrowskiej.