Niektóre elementy układu współczesnej Mdiny, takie jak wąskie i przypominające labirynt uliczki, mogą nadal odzwierciedlać dziedzictwo tego okresu i wykazywać podobieństwo do historycznych medyn w Afryce Północnej.
Bizantyńczycy oblegali Medinę w latach 1053–1054, lecz zostali odparci przez jej obrońców. Miasto poddało się pokojowo Rogerowi I Sycylijskiemu po krótkim oblężeniu w 1091 roku.
W XII wieku fortyfikacje miasta zostały przebudowane i rozbudowane. W tym czasie obszar miasta został już zredukowany do wielkości zbliżonej do obecnej. Teren na południe od miasta, który wcześniej wchodził w skład rzymskiej Melite, a teraz znajdował się poza murami, został przekształcony w przedmieście, czyli dzisiejszy Rabat.
Ludność Malty w XV wieku wynosiła około 10 tys. osób, a życie miejskie ograniczało się do Mdiny, Birgu oraz Cytadeli na Gozo. Mdina była stosunkowo mała i częściowo niezamieszkana, a do 1419 roku została już przewyższona pod względem wielkości przez swoje przedmieście, Rabat. Pod panowaniem Aragończyków władza lokalna spoczywała na Università, wspólnotowym organie z siedzibą w Mdinie, który pobierał podatki i zarządzał ograniczonymi zasobami wysp.