Στις αρχές του 9ου αιώνα, σε μια περίοδο που οι Βυζαντινοί μαστίζονταν από εσωτερικές έριδες κι επιπλέον είχαν στραμμένη την προσοχή τους στους πολέμους με τους Βούλγαρους, ένας νέος κίνδυνος εμφανίστηκε για την κραταιά αυτοκρατορία. Σαρακηνοί πειρατές (μουσουλμάνοι σουνιτικού δόγματος), με επικεφαλής τον Αμπού Χαφέζ Ομάρ Α’ (Απόχαψις για τους Βυζαντινούς), καταλαμβάνουν με χαρακτηριστική ευκολία την Κρήτη και δημιουργούν εμιράτο («Imarah Krit» στα αραβικά).
Στις 7 Μαρτίου 961 ο Φωκάς κατέλαβε τον Χάνδακα κι έθεσε τέλος στην Αραβοκρατία στη μεγαλόνησο, που σήμαινε και την αποκατάσταση της βυζαντινής κυριαρχίας στην Ανατολική Μεσόγειο.
Ο Απόχαψις και οι άνδρες του είχαν καταστήσει την Αλεξάνδρεια της Αιγύπτου ορμητήριό τους από το 816, μετά τη φυγή τους από τη μουσουλμανική Ανδαλουσία. Από εκεί εκστράτευσαν κατά της Κρήτης και με μόλις 20 πλοία κατόρθωσαν να την καταλάβουν, δηλωτικό της χαλαρής στρατιωτικής παρουσίας του Βυζαντίου στο νησί.
Η κατάκτηση της Κρήτης ξεκίνησε το 823 και ολοκληρώθηκε το 828. Οι κατακτητές επέβαλαν ένα στυγνό καταπιεστικό καθεστώς, με βίαιο εξισλαμισμό του πληθυσμού, καταστροφή χριστιανικών ναών, βασανισμούς κληρικών και αναγκαστική στρατολόγηση των νέων. Στόχος τους, η αλλοίωση της θρησκευτικής και εθνικής ταυτότητας της μεγαλονήσου.
Με επίκεντρο τον Χάνδακα (σημερινό Ηράκλειο) πραγματοποιούν επιδρομές τους στα γύρω νησιά και παράλια, αποκομίζοντας πλούσια λεία και δούλους για το δουλεμπόριο της εποχής. Η αραβική κατάκτηση της Κρήτης δεν σήμαινε μόνο την απώλεια ενός σημαντικού στρατιωτικού ερείσματος για τους Βυζαντινούς, αλλά και τη συνεχή απειλή των νησιών και των παράλιων περιοχών της αυτοκρατορίας από τις ληστρικές επιδρομές των Σαρακηνών, με αποκορύφωμα την κατάληψη της Θεσσαλονίκης από τον Έλληνα εξωμότη Λέοντα Τριπολίτη (Ρασίκ αλ Βαρντάμι για τους Άραβες). Η απειλή αυτή έγινε μεγαλύτερη μετά την κατάληψη της Σικελίας από τους Αγλαβίδες εμίρηδες της βόρειας Αφρικής, τους οποίους κάλεσε σύμφωνα με την παράδοση ο στασιαστής βυζαντινός ναύαρχος Ευφήμιος.
Το γεγονός αυτός θορύβησε την Κωνσταντινούπολη, η οποία αποφάσισε να δράσει άμεσα.
Στον «ιερό πόλεμο» των Αράβων το Βυζάντιο αντέταξε τη χριστιανική ιδέα κι έδωσε στις στρατιωτικές επιχειρήσεις το χαρακτήρα «σταυροφορίας», όπως επισημαίνει η διαπρεπής βυζαντινολόγος Ελένη Γλύκατζη-Αρβελέρ. Κύριο μέλημά της, η αναδιοργάνωση του ναυτικού, που θα βοηθούσε σταδιακά την αποκατάσταση της βυζαντινής κυριαρχίας στη Μεσόγειο.
Το 825 ο πρωτοσπαθάριος Φωτεινός μαζί με τον κόμη Δαμιανό οργάνωσαν εκστρατεία, αλλά απέτυχαν. Την ίδια τύχη είχε και η εκστρατεία του στρατηγού Κρατερού το 826, που διέθετε μεγαλύτερες δυνάμεις. Παρότι κατέλαβε αρχικά τον Χάνδακα, δεν απέφυγε τελικά την ήττα. Μάλιστα, οι Σαρακηνοί του επιφύλαξαν και ατιμωτικό θάνατο, σταυρώνοντάς τον ανάποδα. Ακολούθησαν οι αποτυχημένες προσπάθειες για την ανακατάληψη της Κρήτης από τους στρατηγούς Νικήτα Ωορύφα (828), που πάντως ανακατέλαβε τα νησιά των Κυκλάδων, Θεόκτιστο και Σέργιο Νικητιάτη (843).
Από τις αρχές του επόμενου αιώνα οι Βυζαντινοί επανέλαβαν τις προσπάθειές τους για την ανακατάληψη της Κρήτης. Το 911 η μεγάλη εκστρατεία με επικεφαλής τον λογοθέτη του δρόμου Ιμέριο απέτυχε, όπως και η ανάλογη του 956 υπό τον Κωνσταντίνο Γογγύλο. Στην επιχείρηση του Ιμέριου συμμετείχαν και 700 ναύτες Ρως (Ρώσοι), όπως αναφέρει ο Κωνσταντίνος Πορφυρογέννητος.
Η ανάκτηση της Κρήτης επιτεύχθηκε, τελικά, από τον στρατηγό και μετέπειτα αυτοκράτορα Νικηφόρο Φωκά, που είχε πολεμήσει κατ’ επανάληψη τους Άραβες.
Ανέλαβε προσωπικά την ευθύνη για τη διοργάνωση της εκστρατείας, με την έγκριση του αυτοκράτορα Ρωμανού Β΄. Η προετοιμασία της ήταν εντυπωσιακή και αποδεικνύει τη σημασία που αποδιδόταν στη νήσο από την αυτοκρατορία. Σύμφωνα με βυζαντινές πηγές, οργανώθηκε ένας στόλος από 3.300 πλοία για τη μεταφορά οπλιτών (72.000 πεζοί και 5.000 ιππείς) και πολεμικού υλικού. Τα μισά από αυτά τα πλοία ήταν εφοδιασμένα με καταπέλτες για την εκτόξευση του «υγρού πυρός», του στρατηγικού όπλου των Βυζαντινών εκείνη την περίοδο.
Η τεράστια αρμάδα έφθασε στον Χάνδακα στις 13 Ιουλίου 960 και αποβίβασε τους στρατιώτες στη γειτονική ακτή του Αλμυρού. Αμέσως μετά, ο στόλος υπό τον δρουγγάριο Μιχαήλ απέκλεισε από θαλάσσης τον Χάνδακα, ενώ ο Φωκάς εκκαθάρισε τη γύρω περιοχή από τους Σαρακηνούς, αποκλείοντας τον Χάνδακα και από την ξηρά. Μια απόπειρα του αραβικού στρατού των επαρχιών της Κρήτης να σπάσουν τον αποκλεισμό απέτυχε παταγωδώς. Ελάχιστοι διασώθηκαν, οι δε Βυζαντινοί ανταπέδωσαν τη σκληρότητα των Αράβων, αφού ύψωσαν σε ξύλα τα κεφάλια των νεκρών γύρω από τα τείχη του Χάνδακα, για να κάμψουν το ηθικό των πολιορκημένων.
Στις 7 Μαρτίου 961 ο Φωκάς κατέλαβε τον Χάνδακα κι έθεσε τέλος στην Αραβοκρατία στη μεγαλόνησο, που σήμαινε και την αποκατάσταση της βυζαντινής κυριαρχίας στην Ανατολική Μεσόγειο. Οι Βυζαντινοί συμπεριφέρθηκαν με εκδικητική μανία στους ηττημένους. Οι σφαγές και οι λεηλασίες διήρκεσαν πολλές ημέρες, ενώ ο Χάνδακας κατεδαφίστηκε εκ θεμελίων και στη θέση του χτίστηκε μία νέα πόλη, με το όνομα Τέμενος. Ο τελευταίος εμίρης της Κρήτης Αβδούλ Αζίζ Κουρτουμπί (ο Κουρούπης των Βυζαντινών), και ο γιος του Νουμάν (Ανεμάς), συνελήφθησαν και οδηγήθηκαν θριαμβευτικά στην Κωνσταντινούπολη. Τους επόμενους μήνες οι Βυζαντινοί φρόντισαν για τον εποικισμό της Κρήτης, τον εκχριστιανισμό των μουσουλμάνων κατοίκων της και την επαναφορά των εξισλαμισθέντων στη χριστιανική πίστη.
Γνωστοί ασκητές, όπως ο Αθανάσιος ο Αθωνίτης και ο Νίκων ο Μετανοείτε εργάστηκαν με ζήλο για το σκοπό αυτόν.
Μάλιστα, μέρος των τεράστιων θησαυρών που είχαν σωρεύσει οι Σαρακηνοί στον Χάνδακα, δόθηκε στον Αθανάσιο τον Αθωνίτη για την ίδρυση της μονής της Μεγίστης Λαύρας στο Άγιο Όρος.
