Ni znano,
kdaj je bila na ostankih rimskega kastela na Hribu zgrajena prva cerkev. Ve se
le, da je v dolžino merila samo kakih 29 čevljev – 9,16 m. Zidana je bila v poznem srednjem veku. Druga cerkev je
na tem mestu stala v času turških vpadovna ozemlje današnje Slovenije. Znano je, da so morali leta 1526 iz nje oddati
vse bogoslužne predmete, ki so jih prekovali v denar, namenjen za vojno proti
Turkom. Okoli cerkve je bilo pokopališče s kostnico - cerkvico, v kateri je bil
oltar sv. Mihaela. Tudi ta, druga cerkev, je bila majhna; premajhna za takrat
že številčno župnijo. Tako so župljani na škofa Hrena leta 1627 naslovili
prošnjo za graditev nove župnijske cerkve. Ta jim je prošnjo ugodil in že leta
1628 je na Hribu stala nova cerkev.
Četrto stavbo na istem mestu, današnjo cerkev sv.
Pavla, je leta 1852 posvetil ljubljanski knezoškof Anton Alojzij Wolf. Zgrajena
je bila v novoromanskem slogu po
načrtih Josefa Schöbla. Freske v prezbiteriju so delo Janeza Wolfa, ki naj bi za modele upodobljenih figur uporabil
nekatere domačine. Ornamentalne okrase teh fresk je naslikal Janez Borowsky.
Jeseni leta 1907 je celotno cerkev ornamentalno poslikal domači umetnik Simon Ogrin, vendar pa so bile žal ob
prenovi leta 1977 njegove poslikave prebeljene. V cerkvi sicer ostajajo druge
Ogrinove slike: Sv. Družina, kopija Murillovega Sv. Frančiška, Sv. Alojzij,
Božji grob in celoten križev pot. Oltarna slika "Spreobrnitev sv.
Pavla" je delo slikarja Franza Kurza-Goldensteina iz leta 1851.