[1] When the early Muslim conquests began in the 7th century, the Byzantines were threatened in the Mediterranean, so probably efforts were made to improve the defences of Malta.

The Byzantines, having received timely reinforcements, resisted successfully at first, but in 870 Muhammad sent a fleet from Sicily to the island, and the capital Melite fell on 29 August 870.

[8] Most details about the siege of Melite are known from Kitab al-Rawd al-Mitar, which was written by Muhammad bin 'Abd al-Mun'im al-Himyarī in the 15th century.

The invaders wrote to the Aghlabid ruler Abu ‘Abd Allāh, who ordered Muḥammad Ibn Hafāğa, the governor of Sicily, to send a new leader.

[9] Al-Himyarī further states that the island of Malta remained an uninhabited ruin after the siege, at times being visited by shipbuilders, fishermen, and those who collect honey.

The island was repopulated by Muslims in 440 AH (1048–49 AD),[clarification needed] who built a settlement known as Medina on the ruins of Melite.

[3] The use of marble from the churches of Melite in the castle of Sousse is confirmed by an inscription on the castle which translates to:[9][10][clarification needed] Every cut slab, every marble column in this fort was brought over from the church of Malta by Ḥabaši ibn ‘Umar in the hope of meriting the approval and kindness of Allāh the Powerful and Glorious.Although al-Himyarī states that Malta remained an "uninhabited ruin" after the siege and it was only repopulated in 1048–49, archaeological evidence suggests that Mdina was already a thriving Muslim settlement by the beginning of the 11th century, so 1048–49 might be the date when the city was officially founded, possibly the date of construction of the city walls.