Źródła podają, że kościół wzniesiony został pomiędzy XII a XIV wiekiem[6] (prawdopodobnie pomiędzy końcem XIII a pierwszą połową XIV wieku[5]). W najnowszych badaniach wskazuje się na rok 1288 jako datę powstania świątyni[5], w tym też roku świątynia wzmiankowana była po raz pierwszy, przy okazji przekazania zakonowi cysterek[4][6]. Z roku 1343 pochodzi porozumienie, na mocy którego patronat nad kilkoma ołtarzami z prawem do mszy świętych objęła rada miejska. Przed tym rokiem wybudowano dwa wschodnie, krótsze przęsła świątyni[7], a jeszcze w XIV wieku trzy kolejne[7]. Przypuszcza się, że kościół mógł być wzorowanych na podobnych kościołach jak np. na kościele Mariackim w Greifswaldzie[7], jednocześnie pseudobazlikowy układ upodobnił budowlę nieco do katedry w Gorzowie i kościoła w Pyrzycach[7]. Oryginalnie wnętrze kościoła było pokryte sklepieniami krzyżowo-żebrowymi, z wyjątkiem wschodniego przęsła nawy głównej, gdzie zastosowano sklepienia na polach trójkątnych z trójpromieniami[7]. W wieku XV (prawdopodobnie przez osuwanie się gruntu) obiekt został przebudowany[6][8].
W 1535 r. kościół został przejęty przez protestantów, a pierwszym protestanckim pastorem został w 1535 Jan Bugenhagen – rodowity wolinianin i uczeń Marcina Lutra[7]. Po 1560 roku opiekę nad kościołem przejęli książęta ze Szczecina[7]. W czasie wojny trzydziestoletniej, w roku 1628 kościół strawił pożar, a jego odbudowa trwała niemal 100 lat[4] i zakończyła się pod koniec XVII wieku[8]. Podczas odbudowy zrezygnowano z odbudowy sklepień naw, obniżono nawę główną oraz dodano empory nad nawami bocznymi, nadając wnętrzu barokowy charakter. Wieżę odnowiono w 1682 roku[7], odbudowując większość jej struktury[7], a w 1704 roku zakończono remont północnej elewacji[7]. W XVII i XVIII wieku kościół wzbogacił się o liczne elementy wyposażenia, w tym monumentalny ołtarz, który w 1668 roku ufundował Joachim Wolter, oraz późnorenesansową ambonę z 1637 roku, dar Anny Sophii Barkow, żony burmistrza Wolina[7]. Wnętrze zdobiły liczne płyty nagrobne wolińskich mieszczan i rodziny szwedzkiego generała Kagga, a także obrazy tablicowe, w tym portrety pastorów[7].
W połowie XIX wieku stan techniczny budowli był bardzo zły. Według relacji z 1857 roku budowla zaczęła popadać w ruinę[7]. W 1860 roku przystąpiono do remontu, w ramach którego zburzono ściany naw bocznych i postawiono nowe neogotyckie wykonane z cegły fabrycznej, a także częściowo przemurowano ścianę wschodnią[6] i przeprowadzono regotyzację budowli[7].
W roku 1879 dokonano remontu III kondygnacji wieży[6] i jej zwieńczenia[8], oraz umieszczono daty: 1706–1897. W 1898 roku przebudowano wschodni szczyt budynku[7].
Kościół po II wojnie światowej
Podczas II wojny światowej świątynia została znacznie zniszczona[4][6][9]. Zniszczone zostały dach i stropy nad korpusem[7] oraz zwieńczenie i wnętrze wieży wraz z dachem hełmowy na wieży[7][10]. Runęła część wschodniego szczytu[7] i prawie wszystkie filary nawy południowej[7][10]. Uszkodzeniu uległy mury kapitalne korpusu i wieży oraz pozostałe filary wraz ze ścianą arkadową[10]. Mury wzdłużne od ich poprzecznych powiązań rozspoiły się[10]. Pozostały mury obwodowe, ale bez części południowej, elewacja wschodnia i fragment szczytu oraz filary po stronie północnej, jeden filar po stronie południowej i mury obwodowe wieży[6]. Przez lata twierdzono , że kościół zniszczony został wskutek działań wojennych w 80 procentach[4][6], jednak w roku 1945 wojewódzki konserwator odnotował uszkodzenie dachu i łuków naw oraz zniszczenie wieży, a stopień zniszczeń oszacowano na 50 procent[11]. Do początku lat 50. nie podjęto żadnych działań zabezpieczających, co spowodowało znaczne pogorszenie stanu obiektu. W rezultacie zasugerowano rozbiórkę wschodniego szczytu kościoła, a zakres prac rozbiórkowych rozszerzono na inne ściany[11]. W latach 1952–1953 kuria ordynariatu w Gorzowie Wielkopolskim złożyła wnioski do ministerstwa kultury i sztuki oraz konserwatora wojewódzkiego w Szczecinie o „subwencje na odbudowę lub zabezpieczenie zabytkowego kościoła”. Po odwilży w 1956 roku władze wyznaniowe przekazały w całej administracji apostolskiej 73 budowle sakralne, jednak nie zgodziły się na oddanie obiektu w Wolinie. Kościół św. Mikołaja został wpisany do rejestru zabytków w 1959 roku. Biorąc pod uwagę historyczne aspekty, znaczenie dla regionu oraz negatywny wpływ licznych przebudów na przestrzeni wieków, budowla zakwalifikowana została do drugiej grupy[12]. Władze państwowe planowały, że obiekt posłuży celom świeckim, co pozwoliło im zachować nad nim kontrolę[13]. W połowie lat 60. władze konserwatorskie w Szczecinie otrzymały wniosek o zgodę na „odbudowę i adaptację zabytkowej katedry w Wolinie przy ul. Wojska Polskiego, z przeznaczeniem na salę widowiskowo-rozrywkową, której miasto Wolin nie posiadało”[13]. Plan zakładał odbudowę wieży, którą przeznaczono na punkt widokowy, z kioskiem z pamiątkami, biurem PTTK oraz muzeum ziemi wolińskiej. Odbudowa kościoła miała uwzględniać zachowanie jego stylu architektonicznego wewnątrz i na zewnątrz, pozostawiając go jako zabytek, jednak wewnątrz zaplanowano salę widowiskową ze sceną[13]. Władze konserwatorskie poparły inicjatywę[13], ale prac nie rozpoczęto[14]. W latach 1960–1961 obiekt został częściowo odgruzowany przez szczeciński oddział Przedsiębiorstwa Państwowych Pracowni Konserwacji Zabytków[6]. W latach 60. XX wieku władze państwowe nakazały rozebrać częściowo mury dawnej świątyni[15]. W tym samym czasie rozebrano też pozostałości kościoła św. Jerzego.
Odbudowa
W roku 1968 zlecono wykonanie projektu zabezpieczenia kościoła w formie trwałej ruiny[14]. Projekt, przygotowany przez inżyniera architekta Łopacińskiego, przedstawiał dwa alternatywne rozwiązania. W pierwszym wariancie zakładał utworzenie trwałej ruiny poprzez zachowanie murów z pierwotnego etapu budowy – wieży, ściany wschodniej i filarów z arkadami, przy jednoczesnym rozebraniu neogotyckich ścian naw bocznych do fundamentów[14]. Drugi wariant, ze względu na stosunkowo dobry stan murów neogotyckich, przewidywał przykrycie kościoła płaskim dachem w celu użytkowego zabezpieczenia obiektu jako ruiny, bez pełnej odbudowy[14]. Ostatecznie realizacja projektu objęła wariant pierwszy, koncentrując się na wybranych elementach budowli i przystosowaniu wieży do funkcji punktu widokowego[14]. W latach 1971–1972 Zakład Architektury Politechniki Warszawskiej sporządził dokumentację techniczną z koncepcją zabezpieczenia kościoła jako tzw. trwała ruina[6]. Do końca 1971 r. kościół został częściowo zabezpieczony, jednak rok później zburzono (bez uzasadnienia) fragment ściany południowo-zachodniej nawy bocznej, mimo że był w całkiem dobrym stanie[6][14]. Napotkano „trudności techniczne” przy opracowywaniu projektu konstrukcyjnego dla zaakceptowanej koncepcji architektonicznej[16]. Ustalono, że projekt powstanie dopiero po „rozpatrzeniu koncepcji trwałego zabezpieczenia przez Radę Konserwatorską pod kątem zachowania poszczególnych części nawarstwień obiektu”[16]. Widoczny był brak jednolitego stanowiska pomiędzy służbami konserwatorskimi a innymi instytucjami w kwestii ostatecznego projektu dotyczącego przyszłości zrujnowanego kościoła[16]. Ostatecznie w 1973 roku osiągnięto wspólne stanowisko i stwierdzono, że najcenniejszymi elementami obecnej bryły ruin kościoła św. Mikołaja w Wolinie są centralna część ściany wschodniej, zachowane filary z arkadami oraz wieża[16]. W 1974 r. przygotowano projekt techniczny „Taras widokowy na wieży”[16]. Ostatecznie zaankrowano wolnostojące filary nawy południowej[6]. W ścianie północnej założono metalową konstrukcję ściągów[6]. Poza tym wzmocniono pozostałe filary, zamurowano wyrwy, zreperowano koronę arkad i ściany wschodniej, wylano wieniec żelbetowy, zabezpieczono wieżę przez założenie stropów żelbetowych i wyczyszczenie lica wieży z zewnątrz[6]. W roku 1978 odbudowano wieżę kościoła z przeznaczeniem na punkt widokowy[6]. Prace zabezpieczające trwały dość długo i dopiero roku 1980 w Karcie Obiektu Zabytkowego pojawiła się adnotacja „trwała ruina”[17].
Kościół we władaniu kościoła
Do kompleksowej odbudowy i przywracania funkcji sakralnych całemu obiektowi przygotowania rozpoczął proboszcz Andrzej Majewicz[15], a same prace rozpoczęły się w roku 1988, po przekazaniu obiektu ówczesnej parafii świętego Stanisława. Odbudowę kościoła opracowywał architekt Janusz Nekanda-Trepka[15]. Autorami koncepcji odbudowy świątyni, trwającej do 1998 roku, byli: Z. Becker, I. Kukla i Stefan Kwilecki. W 2009 roku wstawiono witraże przedstawiające historię Zbawienia, od Protoewangelii do czasów nam współczesnych, projektu Janusza Sobczyka wykonane w jego pracowni Ars Antiqua[7].
Parafia św. Stanisława w Wolinie erygowana została 1 czerwca 1951 roku, a zmiana siedziby i tytułu parafii nastąpiła 6 grudnia 2000 roku, kiedy był już odbudowany i poświęcony kościół św. Mikołaja. Nieco wcześniej, 15 października, kościół został poświęcony[4].
ks. Roman Kostynowicz: Pomniki architektury sakralnej diecezji szczecińsko-kamieńskiej i kościoły miast biskupich w malarstwie i grafice Wiesława Śniadeckiego. Wyd. 1. Szczecin: Wydawnictwo Polskie Pismo i Książka, 1991.