The archeological clearing of the site has revealed an extensive system of underground galleries and tombs dating from the third to the eighth centuries CE.

St. Paul's catacombs are part of a large cemetery once located outside the walls of the ancient Roman city of Melite, now covered by the smaller Mdina and Rabat.

It is probable that this enlargement joined neighboring tombs and led to the creation of small catacombs, which became the norm by the fourth century CE.

The main complex, covering an area of more than 2,000 square meters (22,000 sq ft), is so far the largest catacomb ever to be found on the island.

The surgical tools carved in relief on one of the three blocking stones in the inner chamber suggest that it was the burial place of a particular family or group of surgeons.