Τα λείψανα του πρωτοβυζαντινού Ηρακλείου είναι λιγοστά, όπως αυτά των παλαιότερων περιόδων. Δομικά στοιχεία και αρχιτεκτονικά μέλη έχουν συνήθως επαναχρησιμοποιηθεί σε μεταγενέστερες κατασκευές. Μπορούμε να υποθέσουμε ότι η πόλη χτυπήθηκε σκληρά από τον σεισμό του 365 μ.Χ.) και το παράκτιο μέτωπό της σαρώθηκε από το τσουνάμι που ακολούθησε, όπως άλλες παράκτιες κρητικές πόλεις. Αλλά η ζωή βρήκε ξανά το δρόμο της, όπως μαρτυρούν τα νομίσματα του δευτέρου μισού του 4^ου και του 5^ου αιώνα. Αρχιτεκτονικά γλυπτά σε δεύτερη χρήση, όπως λυρόσχημα κορινθιακά κιονόκρανα εισαγμένα από τα λατομεία της βυζαντινής πρωτεύουσας αποδεικνύουν ότι η πόλη ήταν ενεργή στον 5^ο και στον 6^ο αιώνα και το θαλάσσιο εμπόριο είχε ανακάμψει. Στρώματα κατοίκησης της πρωτοβυζαντινής περιόδου εντοπίζονται σε μεγάλο βάθος κάτω από μεταγενέστερες επιχώσεις. Στην οδό Κορωναίου, τμήμα ενός επιμήκους οικοδομήματος, ίσως μιας παλαιοχριστιανικής βασιλικής, και άλλα λείψανα βρέθηκαν σε βάθος 8 μ. από την επιφάνεια. Αρχιτεκτονικά γλυπτά είχαν επίσης ενσωματωθεί σε οικοδομικές φάσεις που χρονολογήθηκαν στην περίοδο της αραβοκρατίας. Κεραμική, μικροτεχνία και νομίσματα μαρτυρούν τη διαρκή κατοίκηση της πόλης μέχρι την αραβική κατάκτηση. Πολυάριθμα νομίσματα των αυτοκρατόρων Ηράκλειου (610-641 μ.Χ.), Κώνσταντα Β΄(641-668 μ.Χ.) και Λέοντα Γ΄ (717-741) παρέχουν ενδείξεις για την επιβίωση της πόλης σε μια περίοδο που χαρακτηρίζεται από σημαντική μείωση της νομισματικής παραγωγής. Γραπτή κεραμική τύπου Γόρτυνας, λυχνάρια τοπικής παραγωγής και εισαγμένες χάλκινες πόρπες του 7^ου και 8^ου αιώνα συμπληρώνουν τα νομισματικά στοιχεία, διαμορφώνοντας εικόνα ανθηρής οικονομικής ζωής στην πόλη κατά την περίοδο των αραβικών επιδρομών, σε αντίθεση με την παραδοσιακή αντίληψη περί παρακμής.