Από τον 7ο αι. το νησί μαστίζεται από αλλεπάλληλες πειρατικές επιδρομές, κυρίως των Αράβων, με αποτέλεσμα την παρακμή των παραλιακών οικισμών. Οι κάτοικοι μετακινούνται στην ενδοχώρα, κυρίως σε μικρούς αγροτικούς οικισμούς. Για την αντιμετώπιση της νέας απειλής η Κρήτη οργανώνεται σε Θέμα. Διοικητικό, εκκλησιαστικό και οικονομικό κέντρο του νησιού όμως παραμένει η Γόρτυνα.
Την περίοδο αυτή υπάρχει οικισμός, που ταυτίζεται με το ρωμαϊκό Ηράκλειον, και ανήκει στη δικαιοδοσία της Επισκοπής Κνωσού. Στα Πρακτικά της Ζ΄ Οικουμενικής Συνόδου (786-7) αναφέρεται ο επίσκοπος Ηρακλειουπόλεως Θεόδωρος, τρίτος στη σειρά των ένδεκα επισκόπων Κρήτης. Δεν αποκλείεται, μάλιστα, ήδη από αυτήν την περίοδο να χρησιμοποιείται για τον οικισμό το τοπωνύμιο Κάστρο.
