Κατά την περίοδο της βασιλείας του αυτοκράτορα Μιχαήλ Β΄ (820-829 μ.Χ.), μια μεγάλη ομάδα Αράβων από τη μουσουλμανική Ισπανία έφθασε στο νησί, γύρω στα 824 μ.Χ., με σκοπό τη ληστρική επιδρομή, μια τακτική γνώριμη στους Βυζαντινούς ήδη από τον προηγούμενο αιώνα. Ωστόσο, σύμφωνα με τις βυζαντινές πηγές, ο επικεφαλής των Αράβων, ο Abu-Hafs-Omar, μετά την απόβαση έστειλε το στρατό του στα ενδότερα του νησιού για έρευνες, ενώ ο ίδιος έκαψε τα πλοία του στόλου για να αναγκάσει τους άνδρες του να παραμείνουν στο νησί.
Η ενέργεια αυτή εγκαινίασε την αραβική παρουσία στο νησί, καθώς για πάνω από έναν αιώνα οι Άραβες θα αποτελέσουν τον κυρίαρχο πόλο εξουσίας πάνω στη παλαιά βυζαντινή κτίση. Αν και οι γνώσεις μας είναι περιορισμένες γι’ αυτή την περίοδο, οι όποιες μαρτυρίες αναφέρουν ότι οι Άραβες άσκησαν μία βίαιη πολιτική απέναντι στους κατοίκους του νησιού. Αφού κατέστρεψαν τη Γόρτυνα, οργάνωσαν την πρωτεύουσά τους στο Ηράκλειο, το οποίο ονόμασαν Al Kandaq (πόλη του Χάνδακα), από την τάφρο που κατασκεύασαν γύρω από τα τείχη του. Πολύ γρήγορα η πόλη μετατράπηκε σ’ ένα μεγάλο σκλαβοπάζαρο, με τους Άραβες να ζητάνε λύτρα από τους Βυζαντινούς για την απελευθέρωση των αιχμαλώτων, ενώ και οι ντόπιοι ζούσαν μέσα σ’ ένα κλίμα γενικότερης ανασφάλειας.
Η Εκκλησία δε βρέθηκε σε καλύτερη θέση. Οι επισκοπές καταστράφηκαν και το ποίμνιο έχασε το δεσμό με τους επισκόπους, οι οποίοι δε μαρτυρούνται καν στις λιγοστές έστω γραπτές πηγές. Αν και οι Άραβες κατέστρεψαν την οργανωτική δομή της Εκκλησίας, δε φαίνεται να προχώρησαν σε προσηλυτισμό του ντόπιου πληθυσμού, ούτε να κατέστρεψαν εξολοκλήρου τους χριστιανικούς ναούς. Αυτό ενισχύεται από την πληροφορία ότι σε μια αποτυχημένη εκστρατεία των Βυζαντινών που οργανώθηκε το 843 μ.Χ., ο μάγιστρος Σέργιος Νικητιάτης, που συμμετείχε σ’ αυτήν, παρέμεινε στο νησί και ενταφιάστηκε στη λεγόμενη «Μονή του Μαγίστρου». Το Οικουμενικό Πατριαρχείο επίσης, εικάζεται ότι χειροτονούσε επισκόπους που δεν έμεναν στο νησί, αλλά με τη σειρά τους χειροτονούσαν ιερείς για την ενίσχυση των υπόδουλων Χριστιανών.
Το Βυζάντιο οργάνωσε πολλές εκστρατείες για την απελευθέρωση του νησιού, όπως το 843 μ.Χ., το 911 μ.Χ. και το 949 μ.Χ., που όμως συνεχώς αποτύγχαναν. Ωστόσο, λίγα χρόνια αργότερα, το 960 μ.Χ., επί βασιλείας του Ρωμανού Β΄, θ’ αποβιβαστεί στο νησί ένα μεγάλο εκστρατευτικό σώμα. Αναφέρεται ότι ο παρακοιμώμενος Ιωσήφ Βρίγγας έπεισε τον Ρωμανό Β΄ για το εγχείρημα αυτό, λέγοντας χαρακτηριστικά ότι «και πρέπον εστίν υπέρ των Χριστιανών και ομοφύλων αγωνίζεσθαι». Ο ίδιος μάλιστα αξίωσε να δοθεί η αρχηγία στο δομέστικο των Σχολών της Ανατολής και μετέπειτα αυτοκράτορα Νικηφόρο Φωκά. Τελικώς, μετά από εννεάμηνη πολιορκία, οι Βυζαντινοί κατέλαβαν στις 7 Μαρτίου του 961 μ.Χ. τον Χάνδακα και επανέφεραν την Κρήτη στο βυζαντινό κορμό.