Jak podaje Ferres[4], pierwszy kościół pod wezwaniemśw. Pawła zbudowano na tym miejscu w 1590[1][5]. Akt fundacyjny podpisany został 3 października 1590[6].
Z biegiem czasu kościół został zaniedbany i popadł niemal w ruinę. W 1735 został odbudowany w dzisiejszym kształcie dokładnie w tym samym miejscu. Kamień węgielny nowego kościoła położył 11 sierpnia 1735 biskupPaul Alphéran de Bussan. Jego budowa została ukończona w 1740, a w 1741 ten sam biskup poświęcił świątynię[1][4][5][6].
Budynek kościoła jest zaokrąglony, zbudowano go w stylu doryckim[6].
Wnętrze
W kościele znajdują się trzy ołtarze. Tytularny obraz Nawrócenie św. Pawła to arcydzieło Rokko Buhagiara (ok. 1725–1805) z Bormli[7], ostatniego znaczącego maltańskiego malarza baroku[1]. Na polecenie biskupa Fra Vincenzo Labiniego zastąpił on poprzedni obraz Święty Paweł pędzla Franġisku Zahry[6]. Nad ołtarzem po prawej stronie znajduje się malowidło przedstawiające Męczeństwo św. Barbary nieznanego maarza[7]; niektóre źródła podają jako wykonawcę Francesco Zahrę[4][6][8]. Na drugim ołtarzu znajduje się obraz urodzonego w Bormli Ġanniego Velli Święta Rodzina. Do 11 maja 1919 wisiał tam obraz Święty Franciszek z Paoli[6][8]. W zakrystii znajduje się kopia pracy Mattia PretiegoSpotkanie św. Dominika i św. Franciszka z Asyżu. Kiedyś obraz, razem z zaginionym Wskrzeszenie Łazarza, wisiał obok ołtarza głównego[4][6][7][8].