Obecny kościół katolicki w Szczecinie Żelechowa, powstał z poluterańskiej kaplicy (ufundowana w 1892 r.) stojącej na terenie Cmentarza Brodowskiego (czynnego do 1946 roku). Po zaadoptowaniu kaplicy, nowy kościół został poświęcony przez ks. Dra Świetlińskiego z Towarzystwa Chrystusowego, a pierwszą Mszę św. odprawił 25.12.1946 proboszcz z Golęcina ks. Bruno Stachowiak.

Nowy ksiądz proboszcz objął kanonicznie parafię 7.X.1979r. Pierwszymi współpracownikami byli wikariusze: ks. Zdzisław Koch i ks. Adam Maduzia. Początkowo remontem objęto plebanię., gdzie wymieniono instalację elektryczną, centralne ogrzewanie i kanalizację, oraz zbudowano łazienkę kuchnię. W grudniu 1979r. parafię wizytował ks. bp Jan Gałecki. 

 Rok 1986. W dniach od 4 do 12 października parafianie przeżywali Misje św., które prowadzą OO. Redemptoryści, O. Tadeusz Majgier i O. Stanisław Wójcik z Gliwic. Msze św. odpustową odprawił w naszej parafii ks. prałat Ciepłuch, a Słowo Boże wygłosił ks. dr Zygmunt Wichrowski, prof. Seminarium Szczecińskiego.

 Rozpoczął się Nowy Rok 1989 - rok rosnących napięć społecznych, rok końca komunizmu w Polsce. Ks. bp Majdański 4 czerwca o godz. 16:00 w katedrze udziela alumnom piątego roku święceń diakonatu. Wśród wyświęconych diakonów są dwaj nasi parafianie Krzysztof Frydrych i Henryk Marszałek. W tym dniu odbyły się historyczne demokratyczne wybory do parlamentu. Klęska komunistycznego totalitaryzmu w Polsce. W uroczystość MB Ostrobramskiej przyniesiono z Łodzi płaskorzeźby, które ozdobiły prezbiterium naszego kościoła. Planowane jest przygotowanie nowego wystroju prezbiterium i namalowanie nowego obrazu MB Ostrobramskiej, a także nowe oświetlenie.