Pierwszy drewniany jeszcze kościół zbudowany został tu w 1124 roku, gdy do Szczecina z misją chrystianizacyjną przybył Otton z Bambergu, został jednak spalony podczas najazdu duńskiego w 1189 roku. W latach 1223-37 na jego miejscu zbudowano nową świątynię z cegły.

W 1425 roku rozpoczęła się budowa nowego, gotyckiego korpusu świątyni. Na ścianach zewnętrznych umieszczono maszkarony – twarze autentycznych mieszkańców średniowiecznego Szczecina. W 1460 roku kościół przedłużono ku zachodowi o jedno przęsło, znacznie szersze od pozostałych i zwieńczone wieżą. W 1534 roku w czasie reformacji kościół przejęli protestanci. W 1556 roku rozebrano wieżę, przebudowując zachodnią fasadę. W 1602 roku kościół zwieńczono istniejącą obecnie sygnaturką. W czasie ostrzału artyleryjskiego w 1677 roku został znacznie zniszczony. Odbudowa trwała 24 lata. Po odbudowie była to budowla salowa, bez sklepień i filarów dzielących na nawy. W 1702 roku Hans Kamerling wykonał tzw. pseudosklepienie, czyli drewniany strop ukształtowany na wzór ceglanych sklepień. W 1703 roku szczeciński malarz Ernst Eichner ozdobił sklepienie olbrzymim malowidłem. W 1817 roku podczas remontu usunięto wszelkie elementy barokowe. W 1901 roku dokonano regotyzacji zachodniej fasady świątyni. W 2009 roku w podziemiach świątyni natrafiono na stare pochówki, najprawdopodobniej patrycjatu lub członków dynastii Gryfitów.

Największą ozdobą kościoła jest ciągnący się przez niemal całą długość świątyni plafon z 1703 roku, dzieło Philippa Ernsta Eichnera. Plafon w kształcie wydłużonego prostokąta, o wymiarach 27 x 3 m, z jednej strony zakończony jest półkoliście. Obramowanie plafonu ozdobiono liśćmi akantu w złotym kolorze. Malowidło wykonane jest w technice olejnej i składa się z trzech powiązanych ze sobą scen rozdzielonych powtarzającym się słowem „SANCTUS” – „święty”. Pierwsza scena (znajdująca się przy wejściu do świątyni) przedstawia artystyczną wizję końca świata. W scenie środkowej widzimy tronującego Chrystusa, a po bokach cztery putta wychylające się z otaczających scenę obłoków. Poniżej cztery uskrzydlone postacie z głowami lwa, orła, wołu i człowieka. Scena trzecia przedstawia rzesze ludzi adorujących Baranka na Górze Synaj. Wszystkie trzy sceny stanowią łącznie spójną wizję zgodną z chrześcijańską eschatologią, na którą składa się koniec ziemskiego świata (scena pierwsza), Sąd Ostateczny (scena druga) oraz szczęście zbawionych (scena trzecia).

Na zewnątrz kościoła, (a także w zakrystii) zachowały się konsole w kształcie główek średniowiecznych mieszkańców Szczecina różnej płci i wieku. Niegdyś konsole stanowiły podstawy dla eksponowanych na nich rzeźb. Rzeźby te nie zachowały się. Na północnej, zewnętrznej ścianie kościoła znajduje się nisza jałmużnicza z pierwszej połowy XV wieku, z otworem wrzutowym dla datków. Po obu stronach niszy wbudowano w ścianę kościoła dwie płyty wapienne pochodzące z końca XIV wieku z płaskorzeźbami przedstawiającymi patronów kościoła: św. Piotra i Pawła. Od 1946 roku świątynia należy do wyznawców Kościoła Polskokatolickiego. W 1960 roku dokonano gruntownego remontu świątyni.

Kościół św. Piotra i Pawła znajduje się przy pl. Świętych Piotra i Pawła 4.

Zdjęcia wykonano w maju 2022 roku.