Η αραβική κατάκτηση της Κρήτης διήρκεσε περίπου ενάμισι αιώνα, από το 823/828 ως το 961 μ.Χ. Το επίκεντρο της εγκατάστασης ήταν ο Χάνδακας. Κι όμως μέχρι τα τέλη της δεκαετίας του 1980 κανένα σχεδόν υλικό κατάλοιπο της παρουσίας των Αράβων στην πόλη δεν είχε εντοπιστεί, με εξαίρεση λιγοστά χάλκινα νομίσματα του Εμιράτου από διάφορα σημεία της πόλης στο Αρχαιολογικό Μουσείο Ηρακλείου, λιγοστά χάλκινα νομίσματα από εκσκαφή στην οδό 25^ης Αυγούστου (1955) και στον περίβολο του Αγίου Πέτρου των Δομηνικανών (1967) και τέλος τα λείψανα ενός μικρού, προχειροφτιαγμένου αγροτικού κτίσματος στην Κνωσό, κοντά στην όχθη του Καιράτου, από το οποίο προήλθαν νομίσματα και κεραμική (1971). Η απουσία οικιστικών καταλοίπων ενίσχυσε την αντίληψη ότι οι Άραβες κατακτητές της Κρήτης ήταν κατά βάση πειρατές με διαμονή σε ευτελείς κατασκευές που χάθηκαν χωρίς ίχνη.

Η αύξηση των σωστικών ανασκαφών και τα μεγαλύτερα βάθη εκσκαφών για την ανέγερση πολυώροφων κατασκευών στο ιστορικό κέντρο της πόλης άρχισε να αποκαλύπτει μια εντελώς διαφορετική εικόνα. Τα πρώτα κτηριακά λείψανα με χρήση στους αραβικούς χρόνους βρέθηκαν το 1989 κατά την ανασκαφή οικοπέδου στη συμβολή των οδών Αρκολέοντος και Κορωναίου. Επρόκειτο για δυο συγκροτήματα κτηρίων με μικρά τυφλά δωμάτια, επιμελούς κατασκευής, πιθανόν εργαστηριακοί χώροι. Η ανασκαφή απέδωσε αραβικά νομίσματα, μια γυάλινη σφραγίδα με αραβική επιγραφή, ένα πλούσια διακοσμημένο μπωλ, λύχνους και ακόσμητη κεραμική. Λίγα χρόνια αργότερα, το 1992, κατά τη διάρκεια σωστικής ανασκαφής στον χώρο της Καστέλλας, ανατολικά του ναού του Αγίου Πέτρου των Δομηνικανών, αποκαλύφθηκε τμήμα κτηρίου επιμελούς κατασκευής, σε άνδηρα, με εσωτερική πλακοστρωμένη αυλή, στο δάπεδο της οποίας είχαν καταπέσει πολυτελώς διακοσμημένα αγγεία, γυάλινα και κεραμικά, και ξύλινο κιβωτίδιο με μεταλλικό κάλυμμα που περιείχε εκατοντάδες χάλκινα νομίσματα των Εμίρηδων της Κρήτης. Το εύρημα της Καστέλλας αποτέλεσε το πρώτο αδιαμφισβήτητο υλικό τεκμήριο της ύπαρξης μιας ανθηρής αραβικής εγκατάστασης στον Χάνδακα, επιβεβαιώνοντας τις μαρτυρίες των πηγών για επαύλεις με κήπους και κρήνες.

Στα χρόνια που ακολούθησαν νέα τμήματα της εγκατάστασης ήρθαν στο φως σε ανασκαφές στις οδούς Αλμυρού, Βύρωνος, Βύρωνος & Θαλήτα, Λοχαγού Μαρινέλη,  Παπαγιάμαλη & Κορωναίου και αλλού, τεκμηριώνοντας ότι ο Χάνδακας κατά την αραβοκρατία ήταν πυκνοδομημένος, με καλοφτιαγμένα κτήρια συχνά μεγάλων διαστάσεων, που είχαν ισχυρούς τοίχους, επιχρισμένους με έγχρωμα κονιάματα, εσωτερικές αυλές, κρήνες και πηγάδια, αγωγούς ύδρευσης, αλλά και με εκτεταμένες συνοικίες εργαστηρίων στα οποία παράγονταν τα εξαιρετικής τέχνης τέχνεργα που έρχονται στο φως κατά τις ανασκαφές. Η πόλη είχε μεσαιωνικού τύπου πολεοδομικό ιστό, με ακτινωτά διατεταγμένους δρόμους και φαίνεται ότι αναπτυσσόταν σε άνδηρα, ακολουθώντας την κλίση του φυσικού εδάφους. Ορισμένα από τα κτήρια αποτελούν ενδεχομένως επιβιώσεις ή μετασκευές κτισμάτων της πρωτοβυζαντινής περιόδου (7^ου-8^ου αιώνα) που επλήγησαν από το σεισμό του 795 μ.Χ. με επανάχρηση οικοδομικού υλικού και μαρμάρινων αρχιτεκτονικών μελών.

Τέλος, η πρωτοβυζαντινή οχύρωση της πόλης φαίνεται ότι διατηρήθηκε και συντηρήθηκε από τους Άραβες με την προσθήκη πατητού εξωτερικού επιχρίσματος καστανού χρώματος, που περιείχε τρίχες αιγοπροβάτων. Υπόλειμμα του επιχρίσματος διατηρήθηκε στον πύργο στο Μπεντενάκι. Η μορφή και η σύστασή του αντιστοιχεί στην περιγραφή του Λέοντος Διακόνου («εκ χοός και τριχών αιγείων και υείων… επιεικώς συμπεπιλημένων») και είναι συνήθης στα φρούρια των Ομμεϋαδών στην Ιορδανία και αλλού.