Erst 961 n.Chr. gelang es dem byzantinischen General Nikoforos Fokas, Kreta zu befreien. Iraklion wurden nach viermonatiger Belagerung von den Byzantinern zurückerobert, wobei ungefähr 200.000 Araber ums Leben kamen. Nikiforos Fokas erbaute im Jahre 961 die byzantinische Burg Temenos (Kanli Kastelli), nachdem er Kreta von den Sarazenen befreit hatte. Sein Plan war, die Stadt Hantaka (das heutige Iraklion) nach Temenos zu verlegen, aber es gelang ihm nicht, den Plan zu verwirklichen, und die Stadt blieb, wo sie war. Das Christentum gelangte zu neuer Blüte, und Iraklion wurde zum Erzbistum. Überall auf der Insel wurden Kirchen und Klöster errichtet. Zu den bedeutendsten Kirchen zählen: Panagia Kera in Kritsa; die Rotunda Michael Archangelos, Episkopi; Ai Yannis Kyr-Yannis, Alikianos; Agios Nikolaos, Kyriakoselia; Agios Fanourios vom Moni Varsamonerou; Agios Pandeleimonos, Pigi; und Agios Fanourios, Kitharida. Die wichtigsten Klöster aus jener Zeit sind: Moni Arkadiou, Moni Palianis, Moni Gouverniotissa, Moni Agias Triadas, Moni Gouvernetou, Moni Vrondisi, Moni Agarathou, Moni Toplou, Moni Halep, und Moni Preveli.

Zur gleichen Zeit ließen sich byzantinische Adelsfamilien zusammen mit vielen der Soldaten des General Fokas auf Kreta nieder und bauten neue Dörfer.