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. 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.
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ą.
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ą. 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. 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ą. Zarówno budynki klasztorne jak i sam kościół, były podpiwniczone oraz zbudowane na kamiennym fundamencie. Budynek klasztorny miał wysokość jednego piętra. W roku 1665 wielki pożar miasta 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ą 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.
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. 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 1965 roku rozpoczęto remont budowli prowadzeniem odgruzowania wewnętrznej części ruin. Następnie prowadzono prace budowlane i wyposażenia w poszczególne instalacje, zgodnie z projektem architektonicznym, opracowanym przez mgr inż. arch. J. Majdeckiego z Pracowni Konserwacji Zabytków w Warszawie. W dniu 10 września 1971 roku dokonano uroczystego otwarcia biblioteki, której nadano imię Marii Dąbrowskiej.
