Oba - przedstawione w poprzednim numerze Niedzieli Południowej - staroniwskie obiekty sakralne nie mogły w pełni sprostać wszystkim potrzebom duszpasterstwa parafialnego. Pierwszy, kaplica pw. Narodzenia Najświętszej Maryi Panny, nawet po dobudowaniu przydachu był zbyt mały, by pomieścić większą liczbę wiernych: drugi - kościół pw. Matki Bożej Fatimskiej, choć większy, to jednak ze względu na położenie na obrzeżach parafii nie był akceptowany przez wszystkich parafian, zwłaszcza zamieszkujących inne rejony osiedla. Nadto, jako budowla adaptowana, przez niektórych wiernych uważany był za kościół tymczasowy.
Przedstawione powyżej względy wymusiły podjęcie decyzji o budowie nowej świątyni parafialnej, położonej w centrum osiedla na działce ofiarowanej na ten cel przez rodzinę Trawków, a położonej naprzeciw kaplicy pw. Narodzenia Najświętszej Maryi Panny. Zadanie to podjął ks. Marian Przewrocki, od 1981 r. proboszcz staroniwski. Sytuacja polityczna, a zwłaszcza wprowadzony 13 grudnia 1981 r. stan wojenny, nie ułatwiała mu jego realizacji. Komuniści, którzy z reguły sprzeciwiali się budowie nowych obiektów sakralnych, nie godzili się na wzniesienie drugiego już kościoła na Staroniwie. Ks. Przewrocki, podejmując takie zadanie narażał się na represje służb komunistycznych. Mimo grożącego niebezpieczeństwa rozpoczął przygotowania do budowy świątyni. Najpierw zabezpieczył teren przeznaczony pod kościół, gdyż istniało realne niebezpieczeństwo zajęcia go przez władze komunistyczne. W tym celu wybudował na nim kapliczki, (poświęcone 12 października 1985 r. przez bp. Stefana Moskwę) jako Dróżki Różańcowe. Następnie, architektowi Janowi Bulszy i konstruktorowi Janowi Pietrzykowi, zlecił opracowanie projektu całego kompleksu parafialnego - kościoła, plebanii i zaplecza duszpasterskiego.
Prace budowlane, prowadzone systemem gospodarczym, rozpoczęto od wznoszenia plebanii. Dopiero po zakończeniu tego etapu, (w 1984 r.) zainicjowano budowę kościoła. Bezpośredni nadzór nad pracami sprawowali Tadeusz Dzioch i Stanisław Miazga. Trudności materiałowe, a później kryzys gospodarczy, sprawiły, że realizacja przedsięwzięcia postępowała bardzo wolno. Do 1989 r. - chwili zmiany proboszcza - zbudowana została tylko dolna kondygnacja świątyni. Przystosowano ją do potrzeb kultu i sprawowano w niej służbę Bożą. Dzieło budowy kościoła podjął następca ks. Przewrockiego, ks. Franciszek Dziedzic, któremu w ciągu dziewięciu lat posługi proboszczowskiej w Staroniwie, (do 1998 r.) udało się doprowadzić je do końca. Wznoszenie obiektu zostało zakończone, ale do wykonania pozostało jeszcze wiele zadań, m.in. wystrój kościoła i jego wewnętrzne wyposażenie. Ich realizacją zajął się nowy proboszcz ks. Stanisław Jamiński. Dzięki jego zaangażowaniu i poparciu parafian stosunkowo szybko udało się je zrealizować. Pozwoliło to na uroczyste poświęcenie kościoła, którego dokonał (2 października 1999 r.) ordynariusz rzeszowski bp Kazimierz Górny. Świątynia otrzymała wezwanie Narodzenia Najświętszej Maryi Panny. Aktem tym przeznaczono ją dla celów religijnych.
Kościół jest obiektem dwupoziomowym, o wymiarach 30 x 15 m i wysokości 10,6 m. Nad wejściem wznosi się wieża o wysokości 21 m, zwieńczona krzyżem. Poziom dolny świątyni jest użytkowany jako zaplecze duszpasterskie. Potrzebom kultu służy tylko poziom górny. Posiada on trzy nawy, prezbiterium i obszerny chór. Wystrój wewnętrzny zaprojektował Andrzej Smoczyński z Rzeszowa. W prezbiterium, na ścianie głównej, dominuje motyw krzyża i tabernakulum. Na lewo od prezbiterium znajduje się obraz Jezusa Miłosiernego autorstwa Barbary Smoczyńskiej. Nawy boczne zdobią obrazy Marii Monikowskiej-Tabisz, w prawej - obraz Narodzenia Najświętszej Maryi Panny, w lewej - obraz Matki Bożej Częstochowskiej. Na ścianie głównej prawej nawy bocznej znajduje się obraz Matki Bożej Nieustającej Pomocy, a niszy nawy lewej - figur św. Antoniego, wyrzeźbiona przez Antoniego Bolka z Załęża k. Jasła. W świątyni znajdują się oryginalne, ceramiczne stacje drogi krzyżowej, wykonane, według projektu A. Smoczyńskiego, przez Jerzego Tarnawskiego. Wspomnieć tu należy, że poniżej świątyni, od strony północnej, usytuowane są stacje drogi krzyżowej (wcześniej Dróżki Różańcowe), które zaprojektowała Iwona Matlingiewicz ze Staroniwy, a wykonał z piaskowca Stanisław Samborski z Brzostku.
Trzy obiekty sakralne istniejące obecnie na terenie staroniwskiej parafii z jednej strony ubogacają architekturę osiedla, z drugiej świadczą o wielkim przywiązaniu tamtejszych parafian do wiary, o ich odwadze i ofiarności, a także o dobrej współpracy z kapłanami. Mogą więc zostać nazwane znakami wiary.