In the year ad 60, Saint Paul the Apostle was shipwrecked on Malta and, during a three-month-long stay, he preached the gospel of Jesus Christ to the islanders. In due course, the temple of Juno metamorphosed into a church. A centuries-old tradition, partly proved by archaeological finds, relates how a Roman temple that dominated the site was dedicated by the early Christians to the Virgin Mary. This tradition cannot be taken literally, but the remains of a Roman temple dating from the early imperial period were unearthed in abundance during the building of the present church between 1697 and 1711.
The Romans remained masters until the middle of the fifth century. Malta and Gozo along with Sicily were possibly under the Vandals from about 455 to 476, when they passed first under the Sciri in return for a tribute, and later under the Ostrogoths.
In 535, the islands were conquered by the Byzantines, who ruled until 870. That year they were expelled by the Aghlabid Arabs, who had already conquered Sicily and much of Spain. It seems that the islands were left uninhabited until around 1048, when they were resettled. For reasons of defense, the Arabs inhabited only the former acropolis — the present Iċ-Ċittadella, which they called Mdina.
Any Byzantine church must have perished during the Arab rule (870–1127). In 1127, the islands were conquered by the Normans and then, through marriage and manœuvre, they were inherited in turn by the powerful dynasties of Swabia (1194), Anjou (1266), and Aragon (1282).
The Castrum is mentioned in a report of 1241 when it was the only fortified shelter on the island in times of attack. The term castrum denotes that the edges of the cliffs were presumably fortified and that there was a parish church, dwellings, and some kind of entrance with ditch and drawbridge. A church within the castrum functioning as a parish is attested to in a will made in 1299 by Guillelmus, Vice-Count of Malta.