Około roku 870 wyspy maltańskie zostały zajęte przez Arabów. Miasto przemianowano na Medyna, co doprowadziło do jego obecnej nazwy Mdina. Kopanie fosy Mdiny prawdopodobnie rozpoczęło się za panowania arabskiego.
Malta stała się częścią Hrabstwa Sycylii w 1091 roku, a następnie zdominowana była przez kolejnych feudałów. W ciągu następnych stuleci zostały wprowadzone różne zmiany w murach miasta. Bizantyjska twierdza została przekształcona w zamek, znany jako Castellu di la Chitati. W XV wieku od strony płaskowyżu (dzisiejszy Rabat) system obronny składał się z serii podwójnych murów, czterech wież, w tym Тurri Mastra (znanej również jako Тurri dila bandiera) w pobliżu głównego wejścia oraz Тurri di la Camera w południowo-wschodnim narożniku.
W 1429 roku Saraceni z dynastii Hafsydów podjęli nieudaną próbę zdobycia miasta.
Po 1448 roku w pobliżu głównego wejścia do Mdiny został zbudowany barbakan, ale w 1551 roku został rozebrany. W 1453 roku za królewskim pozwoleniem Castellu di la Chitati został zburzony ze względu na marny stan i nadmierne koszty jego utrzymania.