Dopo l'unione civile e politica delle due comunità di Pedergnaga e Oriano (1964) e dopo l'unione religiosa, avvenuta con Decreto Vescovile del 29 agosto 1965, che sancì la nascita della nuova parrocchia di San Paolo Apostolo, era necessario dare alla comunità un nuova chiesa, che servisse da legame per la comunità dei fedeli.
Fu il primo parroco, Don Emilio Verzeletti, che si fece carico di quest'impegno. Nell'aprile del 1967, una delegazione di parrocchiani assieme a Don Emilio si recò in udienza dal pontefice bresciano Paolo VI. In suo onore, infatti, sia la parrocchia che il paese presero la denominazione di San Paolo. Paolo VI benedì la prima pietra della nuova chiesa parrocchiale, la cui costruzione iniziò il 7 maggio dello stesso anno sul progetto dell'ingegner Zampini.
La chiesa venne inaugurata il 20 settembre del 1968 e dotata di un gonfalone, offerto dal parroco, raffigurante San Paolo. Fu successivamente consacrata in occasione del decennale della sua costruzione, il 20 settembre del 1978, dal Vescovo di Brescia Mons. Luigi Morstabilini. Durante la cerimonia furono inserite nell'altare le S.Reliquie delle due parrocchie, tra cui quelle di S.Andrea, ritrovate da Don Cesare Bonini nel 1915 e traslate in paese da Don Emilio nel 1967.
Nel 1968 fu allestito un altare anche nel parco esterno nel lato occidentale della chiesa, una sorta di chiesa all'aperto, chiamata Valletta Sacra. Essa è visibile anche dall'interno della chiesa attraverso la grande vetrata che percorre tutto il lato ovest della parrocchiale.
Nel 1976 fu dipinto alle spalle dell'altare un affresco raffigurante il Crocifisso dal pittore M° Manenti; nel 1982 ai lati dell'affresco del Crocifisso furono affrescate le figure della Vergine Maria e di San Giovanni apostolo, opera del M° Angelo Pancera. Sulla parete destra, di fianco al presbiterio, furono dipinte sempre dal M° Pancera delle formelle che rappresentano la Via Crucis, disposte in modo da formare una croce.
Nel 1976, in occasione del 50° anniversario di sacerdozio, Don Emilio fece dono alla parrocchia di una statua raffigurante Paolo VI, collocata sul sagrato; in occasione del suo 60° anniversario di sacerdozio, invece, il 29 aprile 1986, Don Emilio donò alla parrocchia una statua dorata di San Paolo, collocata sul tetto della chiesa, a protezione della comunità.
Il successore di Don Emilio, Don Renato Soregaroli, fece dipingere le vetrate della chiesa, lavoro eseguito da Don Giuseppe Fusari intorno al 1990. Nella notte di Natale del 1991 venne collocata una statua di legno della Madonna raffigurante Maria Madre della Chiesa, opera realizzata dallo scultore G.Vincenzo Musner di Ortisei (BZ) e offerta alla comunità da una parrocchiana. Nel 1994, dopo il restauro, venne collocata nel lato destro della chiesa parrocchiale l'antica pala della chiesa di Santa Maria Nascente raffigurante la Natività di Maria (1610), che era stata sostituita nel 1922 con una tela sullo stesso soggetto e che si trovava in stato di degrado in un ripostiglio della chiesa di S.Maria Nascente. Nel 1995 il parroco Don Renato fece restaurare una tela (attribuita al Cossali) raffigurante il Battesimo di Gesù e due Crocifissi lignei, uno dei quali del 1500.
La chiesa subì nel corso degli anni diversi interventi di manutenzione, l'ultimo dei quali tra la fine del 2005 e i primi mesi del 2006, con il rifacimento del soffitto della chiesa.

Presbiterio	Presbiterio	Tabernacolo	Fonte Battesimale
Via Crucis	Interno	Interno	Interno
Vista sul parco dalle vetrate	Presbiterio visto dall'alto	Dall'alto	Dall'alto
Dall'alto	Statua lignea di Maria Madre della Chiesa (1991)	Gonfalone con S.Paolo	Natività di Maria (1610)
Affresco Crocifissione (1976-1982)	Facciata sotto la neve