Byzantine general Nikephoros Phocas liberated Crete from the Arab occupation in 961 A.D. Heraklion fell into Byzantine hands after a four-month siege during which the Arabs suffered approximately 200,000 dead.

Nikephoros Phocas, after liberating Chandax, founded the Temenos fortress on Rokkas hill in 961 A.D., aiming at transferring the city of Heraklion to this location to prevent its citizens from being attacked. During the period of the Byzantine Empire the island began to flourish once more. Its strategic location was established, Heraklion’s position as the capital of the island was strengthened and the arts flourished, mainly through church architecture and icon and mural painting. The murals of this period are especially noteworthy. However, his effort was not completed and the city remained in its original location.

Christianity flourished once more and Heraklion became the seat of the archbishop, while churches and monasteries were built throughout the island. Many of the churches from this period have been preserved throughout the island. Many noble Byzantine families settled on the island during this period, as did many soldiers of Nikephoros Phocas’ army, who built new villages.

After the IV Crusade the Byzantine Empire started to fall apart and during the distribution of the territories Crete initially went to the Genoans and soon after that to the Venetians, who settled on the island.