When the army of Nikoforos Fokas liberated Crete from the Arabs, the island was again united with the Byzantine Empire and entered a new period that lasted 250 years. The main preoccupation of Byzantium was the restoration and stabilization of its authority in the island, and for this purpose it attempted to erase all Arabic influence in the social, political and religious sectors.

In this framework, Byzantium will order the establishment of populations in Crete from other regions of the Empire. During the 2^nd Byzantine period, noble Byzantine families came to Crete from Constantinople and took over the leadership of the island. In order to protect Crete from another possible attack from the Arabs, the Byzantines built fortification walls in various coastal regions. Kydonia was still an important city during the 2^nd Byzantine period and held its strategic location over the hill of Kasteli.
For this reason, Kydonia was one of the regions the Byzantines chose to protect and fortification walls were built in the area over an ancient wall, using the ruins of ancient           Kydonia as building material. Today, only a few parts of the Byzantine walls are preserved in Kasteli. It is also during this period when the city changed its name to "Chania".