Kościół parafialny pw. św. Pawła Apostoła zbudowano w latach 1981–1986 na wschodnim zboczu wzgórza kolanowskiego. Od strony północnej prowadzi do niego ul. Krakowskie Przedmieście, zaś od południa ul. Stanisława Wyspiańskiego. Od samego początku nad budową i wystrojem wnętrza świątyni czuwał ks. prał. Jan Nowakowski – pierwszy proboszcz parafii (w latach 1984-2018).

Miejsce pod budowlę poświęcił abp Jerzy Ablewicz 24 kwietnia 1981 r., podczas Mszy świętej pod przewodnictwem proboszcza bocheńskiego ks. inf. Stanisława Wójtowicza (*1912 †1984), inicjatora budowy kościoła. Uroczystości wmurowania kamienia węgielnego – poświęconego przez papieża Jana Pawła II (*1920 †2005) w Watykanie – przewodniczył 29 czerwca 1982 r. abp Jerzy Ablewicz. Pierwsza Msza święta została odprawiona w piwnicznej części budowanego kościoła – 9 czerwca 1984 r.
29 czerwca tegoż roku, we wspomnienie św. Pawła Apostoła, patrona parafii, odbyła się inauguracyjna uroczystość odpustowa. Poświęcenia kościoła dokonał abp Jerzy Ablewicz 9 czerwca 1985 r., a jego konsekracji abp Wiktor Skworc – 26 września 2004 r.

Kościół św. Pawła Apostoła jest obiektem dwupoziomowym. Górną jego część – przeznaczoną do celów sakralnych – stanowi wysoka na 25 m jednoprzestrzenna nawa z aneksami bocznymi wydzielonymi przez 12 filarów. Po bokach prezbiterium znajdują się dwie kaplice, a od strony wschodniej obszerna platforma chóru organowego. Na tym poziomie od strony zachodniej znajduje się także zaplecze liturgiczne oraz pomieszczenia mieszkalne domu zakonnego. W dolnej części kościoła możliwe jest prowadzenie wielorakiej działalności duszpasterskiej, w czym są pomocne sale o przeznaczeniu konferencyjnym, katechetycznych i wychowawczo-edukacyjnym – największa z nich może pomieścić nawet pół tysiąca osób.
Świątynię o nowoczesnej architekturze na zewnątrz wyróżnia 50-metrowa wieża zwieńczona krzyżem z miedzi patynowanej – jest wysoki na blisko 6 m z ramionami o rozpiętości ponad 3 m. W wieży zawieszono trzy dzwony o imionach: „Maria”, „Stanisław, Jan” i „Józef”, odlane w pracowni ludwisarskiej Jana Felczyńskiego w Przemyślu, a jej praktyczną ozdobą jest dwutarczowy zegar elektroniczny z kurantami.

Głównym projektantem kościoła był architekt krakowski Zbigniew Zjawin (*1921 †1999), rozwiązania techniczne opracował Zenon Piotrowski (*1920 †1986) z Krakowa, kierownikiem budowy w zasadniczej jej fazie był Aleksander Juryk (*1926 †2016) z Bochni. Zewnętrzna elewacja została wykonana na podstawie projektu bocheńskiego architekta Marka Papugi. Wnętrze kościoła jest urządzone wg projektu prof. Józefa Sękowskiego i prof. Czesława Dźwigaja z Akademii Sztuk Pięknych w Krakowie oraz wg koncepcji dr. hab. Dobrosława Bagińskiego z Lublina.

Architekci wnętrza to: prof. Józef Sękowski – twórca prezbiterium (krucyfiks, tabernakulum, relief przyścienny ze św. Pawłem Apostołem) i figur apostołów; prof. Czesław Dźwigaj – autor antepedium ołtarza głównego, ambon, tablicy upamiętniającej konsekrację świątyni oraz zacheuszy; dr Józef Furdyna – autor witraży (wykonanych w krakowskim zakładzie Anny i Ireneusza Zarzyckich) oraz tryptyku w kaplicy MB Fatimskiej; prof. Lucjan Orzech – twórca drogi krzyżowej i cyklu obrazów o żywocie
św. Pawła Apostoła; Marek Benewiat – wykonawca chrzcielnicy, lichtarzy na świece ołtarzowe i paschał; Kazimierz Klimkiewicz – twórca drewnianych rzeźb na ścianach ołtarzowych kaplic MB Fatimskiej i Miłosierdzia Bożego; Janusz Antosz – wykonawca obrazu Jezusa Miłosiernego; Jacek Osadczuk – autor dębowej rzeźby św. Jana Pawła II (także wykonawca kamiennego pomnika św. Pawła Apostoła na placu kościelnym); dr hab. Dobrosław Bagiński – aranżer miejsca kultu św. Jana Pawła II; Andrzej Peller – autor drewnianych ław i konfesjonałów; Łukasz Sękiewicz – wykonawca drewnianej figury św. Rity oraz pamiątkowej tablicy z racji 30. rocznicy powstania parafii i śmierci inicjatora budowy kościoła; Andrzej Strach – autor tablicy upamiętniającej 25-lecie pontyfikatu papieża Polaka; pracownia czeskiej firmy Rieger-Kloss – wykonawca prospektu organowego.