Istniejący kościół zbudowany został w 2 poł. XV w., na miejscu starszej świątyni wzmiankowanej w dokumencie z 1286 r. W tym to roku biskup Herman von Gleichen przyznał prawo patronatu nad kościołem szczecińskiej kolegiacie NMP. W 1489 r., patronat przekazano zakonowi augustianów z Jasienicy i prawdopodobnie po tej dacie rozpoczęto budowę zachowanego do dziś kościoła.

Po 1534 r., patronat objęła Fundacja Mariacka ze Szczecina. Wtedy również kościół stał się świątynią protestancką. W czasie Wojny Trzydziestoletniej świątynia została częściowo zniszczona. Do odbudowy przystąpiono dopiero w 1683 r., wznosząc od nowa górną partię wieży, dach i strop nad nawą. Elewacje otynkowano, powiększono okna, do elewacji południowej dobudowano kruchtę w konstrukcji szkieletowej. Datę przebudowy umieszczono na belce nowego stropu. W tym czasie kościół podporządkowano parafii w Stołczynie. Ołtarz ambonowy ufundowano na początku XVIII w. W latach 1751 i 1765 Johann Heinrich Schell ze Szczecina odlał dwa dzwony ufundowane przez opiekunów kościoła. W drugiej połowie XIX w., wymieniono odeskowanie górnej kondygnacji wieży i przemurowano blendy w szczycie wschodnim. W latach trzydziestych XX wieku wymieniono odeskowanie wieży wycinając dodatkowe otwory. Wtedy również do elewacji wschodniej dobudowano zakrystię i kotłownię z kominem na osi środkowej szczytu. Zakrystię skomunikowano z nawą przejściem przy narożniku południowym.

Po II Wojnie Światowej kościół przekazano parafii rzymskokatolickiej i poświęcono 11 sierpnia 1946 r.

W 1957 r., w Skolwinie ustanowiono parafię. W 1960 r., rozpoczęto remont, podczas którego usunięto wypełnienie stropu, a więźbę obito płytami pilśniowymi, usunięto empory boczne założono nowe posadzki, przeniesiono schody spod empory do kruchty, przebudowano ambonę i ołtarz główny, pomalowano wnętrze. W 1965 r., odsłonięto fundamenty, zasypano gruzem i zalano betonem, wykonano nowe tynki na elewacjach, wymieniono pokrycie dachu z dachówki na blachę i splantowano teren cmentarza. W 1976 roku wykonano konfesjonały i ławki. W latach 1975-1977 założono zieleniec na dawnym cmentarzu przykościelnym.

W latach 1992-1993 skuto tynki z elewacji. Po 1993 roku rozebrano kruchtę przy elewacji południowej i na jej miejscu zbudowano zakrystię wg. projektu architekta szczecińskiego Juliusza Prandeckiego. Prace wykonywała ekipa ze Skolwina sposobem gospodarczym. W czasie realizacji zmieniono kształt okien (projektowane były ostrołukowe) i nie wymurowano sterczyn przy szczycie. We wnętrzu skuto tynki na ścianie wschodniej i na ścianach kruchty podwieżowej, odsłonięto portal prowadzący z nawy do dawnej kruchty, oraz skuto tynki z ościeży portalu w ścianie północnej i przy ościeżach okien w obu elewacjach podłużnych. W kruchcie podwieżowej założono nowy belkowy strop.

W 2003 r. ufundowano tablicę poświęconą pamięci pierwszego proboszcza parafii Chrystusa Króla w Skolwinie ks. Kanonika Henryka Świerkowskiego.

W 2007 r. ufundowano tablice upamiętniająca nazwiska trzech kapłanów z parafii w okresie pięćdziesięciolecia parafii oraz ufundowano „Drogę Krzyżową" ufundowaną przez Sybiraków, a wykonaną przez ks. Marka Cześnina.

Wiosną 2008 r., zdemontowano hełm wieńczący latarnię wieży. Przyczyną był bardzo zły stan techniczny drewnianej konstrukcji, której nie udało się ocalić. Zachowano tylko żelazną sztycę z krzyżem.

W roku 2010 odtworzono iglicę i wyremontowano drewnianą część wieży. Projekty remontu kościoła, sporządzone przez Agnieszkę Latour, wspólfinansował Urząd Marszałkowski.

Aktualnie trwa remont dachu i przywracanie dachówki. Remont wieży i dachu finansowany został przez Miasto Szczecin na podstawie Karty ewidencyjnej zabytków architektury i budownictwa, WUOZ Szczecin 2008.