Parafia prawosławna świętych apostołów Piotra i Pawła w Stargardzie Szczecińskim jest jedną z młodszych w diecezji wrocławsko-szczecińskiej. Już w 1946 r. w Stargardzie odbywały się sporadyczne nabożeństwa sprawowane w prywatnym pomieszczeniu. Opieką duszpasterską otaczali prawosławną społeczność duchowni posługujący w parafii w Szczecinie. Pierwsze starania o utworzenie parafii w Stargardzie poczyniono w 1949 r., powierzając organizację struktur ks. Janowi Reszetce. Tworzenie parafii zostało zablokowane przez ówczesne władze.
Ponowne próby zostały podjęte w 1952 roku, lecz także nie przyniosły pożądanych efektów. Dopiero w listopadzie 1954 r. Cerkwi prawosławnej przyznano obiekt w Stargardzie. Był to poewangelicki, neogotycki kościół, zbudowany na planie krzyża greckiego, znajdujący się w centrum miasta. Zanim jednak oficjalnie Cerkiew przejął ten obiekt, Kuria rzymskokatolicka w Gorzowie starała się wstrzymać, a nawet cofnąć decyzję przekazania świątyni. Urząd do Spraw Wyznań nie zmienił jednak stanowiska w tej sprawie i w grudniu 1954 r. obiekt należał już do Cerkwi prawosławnej.
Po przystosowaniu obiektu na potrzeby prawosławnej świątyni, w marcu 1955 r. zostało odprawione pierwsze nabożeństwo. Część wyposażenia stargardzkiej cerkwi pochodziło ze zlikwidowanej parafii w Kijowcu (pow. Biała Podlaska).
W latach 50. XX w. stargardzka parafia skupiała około 90 rodzin. W większości byli to ludzie, którzy zostali przesiedleni na ziemie zachodnie podczas akcji „Wisła”. Były także osoby, które przyjechały za pracą na nowe ziemie odzyskane. Pierwszym proboszczem stargardzkiej parafii był ks. Juwenaliusz Wołoszczuk, niosący posługę w latach 1954-1961. W latach 1961-1966 posługę duszpasterską niósł ks. Grzegorz Ostaszewski. Szczególną radość parafia przeżywała 12 lipca 1964 r., gdy podczas święta ku czci świętych apostołów Piotra i Pawła dokonano poświęcenia cerkwi przez metropolitę warszawskiego i całej Polski Bazylego.
Z roku na rok stargardzka świątynia wymagała coraz pilniejszych prac remontowych. W latach 2008-2010 udało się wymienić pokrycie dachu i dokonać częściowych napraw elewacji. Jednak wnętrze wymagało pilnych prac. 4 września 2010 r. proboszczem parafii został ks. Jarosław Biryłko, który poczynił uwieńczone sukcesem starania o pozyskanie dotacji na remont ze środków unijnych. Kapitalny remont odbył się w latach 2011-2012.
(Ks. Jarosław Biryłko. Skrócona wersja artykułu opublikowanego w „Wiadomościach Polskiego Autokefalicznego Kościoła Prawosławnego” 2012, nr 3.)