Κατά τη διάρκεια των μεταβατικών χρόνων (7^ος-8^ος αιώνας μ.Χ.) τόσο στον ελλαδικό χώρο όσο και στις ανατολικές περιοχές της αυτοκρατορίας παρατηρείται η επισκευή και η συμπλήρωση προγενέστερων οχυρώσεων με κοινό χαρακτηριστικό τη χρήση αρχαιότερου οικοδομικού υλικού, μετά τις εκτεταμένες καταστροφές που προκλήθηκαν από τα σοβαρά σεισμικά γεγονότα του 7^ου και 8^ου αιώνα και τις εντεινόμενες εχθρικές επιδρομές.

Η εμφάνιση της Αραβικής απειλής στο Αιγαίο από το 649 μ.Χ. και η σταδιακή απώλεια των βυζαντινών επαρχιών που τροφοδοτούσαν με πρώτες ύλες την πρωτεύουσα και το βυζαντινό στράτευμα ανέδειξε τη στρατηγική θέση της Κρήτης ως πηγής ανεφοδιασμού της πρωτεύουσας και κατέδειξε την ανάγκη προστασίας των εμπορικών δρόμων που την συνέδεαν με την Κωνσταντινούπολη. Μέσα στα πλαίσια αυτά επιχειρήθηκε από τα μέσα του 7^ου αιώνα και στη διάρκεια του 8^ου η διοικητική ανασυγκρότηση του νησιού και η αμυντική του θωράκιση με την ανακατασκευή των παλαιότερων οχυρώσεων ή την κατασκευή νέων.

Σ’ αυτό το πλαίσιο, η ανακατασκευή της ελληνιστικής οχύρωσης του Ηρακλείου μετά τα μέσα του 7^ου αιώνα, όπως τεκμηριώνεται από την ανασκαφική έρευνα στο Μπεντενάκι, ήταν κρίσιμη για την προστασία της πόλης και του λιμένα της. Η κατασκευή της πρωτοβυζαντινής περιόδου διακρίνεται με σαφήνεια από την προηγούμενη: ο εσωτερικός πυρήνας αποτελείται από αργολιθοδομή και η εξωτερική όψη από λαξευτούς λίθους της ελληνιστικής περιόδου, που έχουν κοπεί και κατάλληλα συναρμοστεί. Άφθονο κονίαμα από ασβέστη, βότσαλα και κουρασάνι έχει χρησιμοποιηθεί ως συνδετικό υλικό και διάσπαρτα θραύσματα πλίνθων συμπληρώνουν τους αρμούς. Η ίδια τεχνική κατασκευής παρατηρείται σε μια σειρά οχυρώσεων της ίδιας περιόδου σε όλο το νησί, όπως στη Γόρτυνα, την Κυδωνία (Χανιά) και την Ελεύθερνα.

Η οχύρωση, που θεμελιώθηκε στα λείψανα της ελληνιστικής, ακολούθησε την πορεία της, περιβάλλοντας την πόλη και τον λιμένα, φτάνοντας στα δυτικά τουλάχιστον ως την οδό Χάνδακος, στα νότια ως την οδό Δαιδάλου και στα ανατολικά ως την οδό Μποφώρ. Λείψανά της διατηρούνται σε διάφορα σημεία, ενσωματωμένα στις οχυρώσεις της Βενετοκρατίας. Η νότια και νοτιοδυτική πλευρά της ίσως περιβαλλόταν εξαρχής από τάφρο, όπως συνέβαινε στην Κυδωνία. Η ύπαρξη της τάφρου αντανακλάται στο όνομα που έδωσαν στην πόλη οι Άραβες, πιθανότατα πριν ακόμη την κατακτήσουν: Rabd el Khandaq, το φρούριο της τάφρου.