Recent evidence shows that the city of Heraklion was already fortified in the Hellenistic period. As part of a generated defensive plan aiming to confront the increasing Arab threat, the enceinte was reconstructed by the Byzantines in the 7th or 8th c. A.D. with a large amount of reused ancient blocks. The enceinte had vertical walls and quadrangular towers and it was protected by a moat, which gave to the city its long lasting Arab name, Rabdh el-Chandaq (the fortress of the moat), turned into Chandax in the Middle Byzantine period and into Candia during the Venetian period. The Arabs reinforced the enceinte using an external coating made of mortar mixt with animal hair, that was revealed in recent excavations. When Nicephoros Phokas recaptured the city in 961, he demolished parts of the enceinte to neutralize its defensive capability. It is though still traceable, incorporated in the remains of the older enceinte, which was restored by the Venetians after their settlement in 1211.