Il-Knisja Kolleġġjata Bażilika ta’ San Pawl hi mibnija fuq il-foss tal-belt Rumana Melita li kienet tħaddan ukoll parti sewwa mir-Rabat. Hi wkoll mibnija fuq għar fejn skont tradizzjoni qadima kien jgħammar San Pawl tul it-tliet xhur li dam Malta fis-sena 60 w.Kr. Fl-1336, l-Isqof ta’ Malta, Ilarju, sejħilha ecclesia Sancti Pauli de crypta u semma wkoll iċ-Ċimiterju u l-foss tagħha. Tul is-snin inbnew żewġ knejjes fuq dan l-għar mill-Ordni ta’ San Ġwann iddedikati lil San Publiju. Il-knisja ta’ San Pawl li hemm illum inbniet bil-ġenerożitá tan-nobbli Guzmana Navarra fuq il-pjanta ta’ F. Bonamico fl-1653 u tlestiet minn Lorenzo Gafà fl-1683. Din inbniet flok oħra medjevali.