First Byzantine Period (330 - 961)

As part of the Eastern Roman Empire, Crete was left to the Byzantine Empire, of which it became an administrative region, with Gortyn as its capital. In early Byzantine times (4^th - 6^th centuries), the island lived in prosperity and peace, but from the late 6^th century onwards the earlier urban centres fell into decline and the population moved into the countryside. The Arabs had control of the trade routes to the East, and external trade began to wane.

From the 7^th century onwards the island was subject to repeated pirate raids, led mainly by the Arabs, which brought about the decline of coastal settlements. The inhabitants moved inland to small farming settlements. To deal with this new threat Crete was upgraded to a theme, with Gortyn remaining the administrative, ecclesiastical and economic centre.

In this period there was a settlement identified as Roman Herakleion, which came within the jurisdiction of the Diocese of Knossos. Theodoros, Bishop of Herakleioupolis, is referred to in the Proceedings of the VI Oecumenical Council (786-7) as being third in the hierarchy of the eleven bishops of Crete. By this time Kastro may well have been in use as a place name for the settlement.