Katakumby św. Pawła to najstarsze archeologiczne świadectwo chrześcijaństwa na Malcie. Znajdują się one na obrzeżach starej rzymskiej stolicy Melite (dziś Mdina), ponieważ rzymskie prawo zakazywało pochówku w granicach miasta. Zespół wydrążonych w skale połączonych ze sobą, podziemnych cmentarzy był w użyciu aż do IV wieku naszej ery. Fragmenty katakumb były używane powtórnie podczas ponownej chrystianizacji wyspy dziewięć wieków później. Cmentarz został ostatecznie opuszczony, ale podczas II wojny światowej wydrążono nowe tunele. Które wykorzystywano jako schronienie podczas nazistowskich nalotów.
Inny prywatny schron przeciwlotniczy znaleźliśmy w Casa Rocca Piccola.
Stół agape był powszechnie spotykany w wielu katakumbach na Malcie. Składa się on z wyciętego w skale stołu otoczonego płaską powierzchnią do siedzenia. Pierwsi chrześcijanie używali go do szczególnych posiłków określanych jako uczta Agape (uczta miłości), które odbywały się w pobliżu grobowców w rocznice śmierci bliskich. Był to wyraz oddania czci i braterskiej miłości.
Połączone z katakumbami są Grota św. Pawła i kościół jego imienia. Według Dziejów Apostolskich, podczas podróży św. Pawła z Krety do Rzymu, to właśnie tutaj schronił się on i spędził 3 miesiące po tym, jak jego statek rozbił się na wybrzeżu Malty. Grota stała się jednym z najwcześniejszych miejsc kultu chrześcijańskiego na wyspie. Do dziś jest to ważne miejsce pielgrzymek dla wielu katolików, nawet papieży.
