Jabarkan Tembok Abad Pertengahan dari Benteng Mdina

Saat runtuhnya Kerajaan Romawi Barat, pembangunan pertahanan kembali dibuat di kota ini, memperkecil ukurannya dibanding saat ini. Ini dilakukan untuk mempermudah pertahanan, seperti juga yang dilakukan di kota-kota lain di sekitar Mediterania pada abad pertengahan. Meskipun secara tradisional diasumsikan bahwa tindakan ini dilakukan Bangsa Arab, namun kemungkinan Romawi Timur-lah pelakunya, saat ancaman Bangsa Arab meningkat.

Pada tahun 870, Melite dikuasai oleh Aghlabid, yang membantai penghuninya dan menghancurkan benteng kota berdasar kronik yang dibuat Al-Himyarī. Inilah yang menjadi dasar klaim bahwa Malta tidak memiliki penghuni hingga sekitar 1048 sampai 1049, saat komunitas muslim dan budak-budaknya membangun pemukiman yang disebut Mdina (Medina) di atas rereuntuhan Melite. Bukti arkeologis memperlihatkan bahwa kota ini sudah menjadi komunitas muslim yang berkembang pada sekitar abad 11. Romawi Timur mengepung Medina pada tahun 1053–54, tetapi mengalami kegagalan.

Medina menyerah secara damai kepada Roger I dari Sisilia setelah pengepungan singkat pada tahun 1091, Malta kemudian bergabung dengan Keresidenan Sisilia, yang kemudian menjadi Kerajaan Sisilia.

Benteng Mdina dibangun ulang dan dimodifikasi beberapa kali selama beberapa abad. Sebuah kastil bernama Castellu di la Chitati alias castrum civitas dibangun di tenggara kota di dekat gerbang utama. Kota ini berhasil bertahan dari Pengepungan Malta pada 1429 oleh Dinasti Hafsid.

Pada abad 15, kebanyakan wilayah Mdina sudah dilindungi tembok ganda. Bagian depan dilindungi empat menara, satu di dekat Gerbang Yunani, lainnya di tengah lahan depan, Turri Mastra di dekat gerbang utama, dan Turri di la Camera di sudut tenggara. Pada tahun 1450, karena ketakutan dengan serangan Kaum Bar Bar atau Utsmaniah, tembok semakin diperkuat. Parit pertahanan diselesaikan dan Castellu di la Chitati sebagian dihancurkan dengan izin kerajaan karena sudah tua dan lapuk serta pemeliharaan yang mahal.