Πάνω στη λίθινη κρηπίδα και τα εναπομείναντα τμήματα του αραβικού φρουρίου, ήρθαν στη συνέχεια οι Βυζαντινοί με τον Νικηφόρο Φωκά (961 - 1204) να ορθώσουν το δικό τους οχυρωματικό περίβολο και να τον επεκτείνουν πάνω στην πορεία που είχε οριοθετηθεί από τους Άραβες στις σημερινές οδούς Χάνδακος, Δαιδάλου, Δουκός Μποφώρ επεκτείνοντάς το και στο θαλάσσιο μέτωπο.

Τα βυζαντινά τείχη αποτελούνταν από τετράγωνους, κατά κανόνα, πύργους με ενδιάμεσα κατακόρυφα ευθύγραμμα τμήματα με οδοντωτές απολήξεις και επάλξεις. Από την πλευρά της θάλασσας μέχρι το λιμάνι το βυζαντινό τείχος είχε οδοντωτό θωράκιο, πύργους κατά αποστάσεις και κυματοθραύστες στη βάση για να προστατεύεται από τη σφοδρότητα των κυμάτων.

Ο οχυρωματικός περίβολος συμπληρωνόταν με τέσσερις πύλες: την πύλη του Κάστρου ή πύλη του Φόρου (Πορτόνε), που βρισκόταν στη νότια πλευρά της πόλης (τέλος της σημερινής λεωφόρου Μαρτύρων 25ης Aυγούστου), την πύλη του Μόλου προς το λιμάνι, την Ωραία πύλη ανατολικά (στην αρχή της σημερινής οδού Δαιδάλου), και την Εβραϊκή πύλη προς τα δυτικά, κοντά στον κόλπο του Δερματά.