Intitolata alla Conversione di San Paolo, è stata anche l’unica parrocchia della città fino al 1954. La chiesa parrocchiale di San Paolo apostolo sorge nella parte più alta del centro storico, ricalcando l’area dove in epoca romana sorgeva un tempio dedicato, con ogni probabilità, ad Ercole.
L’impianto con il quale oggi si presenta fa risalire alla metà del XVIII secolo, testimoniato anche da un’epigrafe che si nota su un arco interno e che riporta l’anno 1747, anche se con ogni probabilità si riferisce ad un restauro o una riconsacrazione dell’edificio, che doveva risalire quantomeno ad epoca bassomedievale, forse usata come cappella palatina dei Giudici di Gallura. Nel 1939 un ulteriore intervento ha modificato la struttura originale che da rettangolare, con tre cappelle per lato, viene trasformata a chiesa con pianta a croce latina, con transetto e cupola.

Nel fare ciò si abbattè l’antico oratorio della Confraternita della Santa Croce, addossato al lato meridionale della parrocchiale. Al posto dell’oratorio che si presentava con volte a sesto acuto in stile gotico-catalano, sorse un edificio adibito a sala polifunzionale.
Agli inizi degli anni Novanta del XX secolo si decise di ristabilire l’antica chiesa della confraternita, riadattando quell’edificio e munendolo di un campanile a vela. 

Al suo interno la chiesa di San Paolo mostra  alcuni oggetti d’arte alquanto pregevoli, quali il coro e il pulpito in legno del Settecento. Fra gli argenti sacri custoditi nella sacrestia, si distinguono i sandali e l’aureola d’argento dell’Assunta, che pare siano opera di un ignoto artigiano sardo del Seicento, ed un elegante ostensorio settecentesco di provenienza palermitana.