Όταν οι Άραβες κατέλαβαν την Κρήτη το 824, ίδρυσαν την πρωτεύουσά τους στη θέση του Κάστρου, του μικρού βυζαντινού οικισμού.
Σύμφωνα με τον Λέοντα τον Διάκονο (10ος αι.), το φρούριο της αραβικής περιόδου προστατευόταν από τη μια πλευρά του από τη θάλασσα, ενώ από τις άλλες είχε τείχος ισχυρό, θεμελιωμένο πάνω σε βραχώδη επιφάνεια με λίθινη βάση. Ο ίδιος αναφέρει ότι οι Άραβες έκτιζαν το τείχος από πλίνθους φτιαγμένους από χώμα και τρίχες από κατσίκια και χοίρους. Το τείχος είχε τέτοιο πλάτος, ώστε μπορούσαν να τρέχουν συγχρόνως δύο άμαξες σε αντίθετη κατεύθυνση.
Γύρω από το φρούριο, που αποτελείτο από ευθύγραμμα τμήματα και πύργους, είχαν ανοίξει δύο πλατιές και βαθιές τάφρους, που το περιέζωναν, δίνοντας συγχρόνως και το όνομα στην πόλη, Ραμπντ Ελ Χαντάκ - Χάνδαξ -Χάνδακας ή Φρούριο της Τάφρου.
Το αραβικό φρούριο στην Τυνησία του 9ου αιώνα, που πιθανόν προσομοιάζει με το φρούριο του Χάνδακα, 2000 (συλ. Χρυσούλας Τζομπανάκη)