Zwischen 824 und 827 eroberten muslimische Verbannte aus Al-Andalus, die zuvor Alexandria in Ägypten besetzt und sich dort niedergelassen hatten, schrittweise Kreta. Sie wurden von Abu Hafs Umar angeführt, der in byzantinischen Quellen als Apohapsis bezeichnet wird. Auf der Insel gründeten sie einen weitgehend selbstständigen muslimischen Staat, das Emirat von Kreta, das bis zur byzantinischen Rückeroberung im Jahr 961 bestand.

Die neuen Herrscher gründeten und befestigten an der Nordküste die Stadt Chandax an der Stelle des heutigen Heraklion. Der Name stammte vom arabischen Wort al-khandaq, das Graben oder Schutzgraben bedeutet, und bezog sich auf den großen Verteidigungsgraben rund um die Befestigungen. Chandax entwickelte sich zur Hauptstadt des Emirats, zu einem bedeutenden Handelshafen und zu einem mächtigen Flottenstützpunkt im östlichen Mittelmeer.

Von Kreta aus wurden Überfälle auf byzantinische Inseln, Schiffe und Küstengebiete unternommen. Seehandel, Piraterie und der Handel mit Gefangenen, von denen viele als Sklaven verkauft wurden, entwickelten sich zu bedeutenden Einnahmequellen des Emirats. Gleichzeitig stärkte die strategische Lage der Insel an den Seewegen des Mittelmeers ihre Handelsbeziehungen zu Ägypten, Nordafrika und der übrigen islamischen Welt.

Der Verlust Kretas stellte für das Byzantinische Reich ein schwerwiegendes strategisches Problem dar, da die Insel als Ausgangspunkt für Angriffe im Ägäischen Meer diente. Die Byzantiner unternahmen wiederholt Feldzüge zur Rückeroberung, doch die meisten scheiterten. Einer der größten erfolglosen Versuche fand im Jahr 949 statt.

Im Jahr 960 begann unter dem Feldherrn Nikephoros Phokas, dem späteren byzantinischen Kaiser, ein neuer großer Feldzug. Das byzantinische Heer landete auf Kreta und belagerte Chandax mehrere Monate lang. Im März 961 wurde die Stadt erobert. Damit endete das Emirat von Kreta und die Insel wurde wieder in das Byzantinische Reich eingegliedert.