Chociaż tradycyjnie zakładano, że obwarowania zostały zbudowane przez Arabów, sugerowano również, że w rzeczywistości wzniesione zostały około VIII wieku przez Cesarstwo Bizantyjskie, gdy zagrożenie ze strony Arabów wzrosło.

W 870 roku bizantyńska Melite, którą rządził namiestnik Amros (prawdopodobnie Ambrosios), została oblężona przez Aghlabidów dowodzonych przez Halafa al-Hādima. Zginął on w trakcie walk, a z Sycylii wysłano Sawādę Ibn Muḥammada, aby kontynuował oblężenie po jego śmierci. Czas trwania oblężenia nie jest znany, ale prawdopodobnie trwało ono kilka tygodni lub miesięcy. Po zdobyciu Melite przez najeźdźców mieszkańcy zostali wymordowani, miasto zniszczone, a jego kościoły splądrowane. Marmur z kościołów Melite został wykorzystany do budowy zamku w Susie.

Według Al-Himyarī Malta pozostawała prawie niezamieszkana aż do ponownego zasiedlenia w 1048 lub 1049 roku przez muzułmanów z Sycylii i ich niewolników, którzy na miejscu Melite zbudowali osadę nazwaną Madina. Dowody archeologiczne sugerują, że na początku XI wieku miasto było już dobrze rozwiniętą osadą muzułmańską, więc lata 1048–1049 mogą oznaczać datę jego oficjalnego założenia i wzniesienia murów miejskich. Układ nowego miasta był całkowicie odmienny od starożytnego Melite.