Based on the masonry of the walls surrounding Kastelli Hill, the first fortifications at the city of Chania or ancient Cydonia date back to the Hellenistic period. The later Byzantine wall is associated with the recapture of Crete by Nicephorus Phocas in 961, and the programme instigated by the Byzantines to rebuild and fortify key positions in Crete and the Aegean region. The topology of the hill appears to have forced the Byzantine fortifications to follow the course of the ancient wall. The main building material was reused stone from ancient Cydonia, as the city was largely destroyed after the period of Arab rule (824-961).

The wall has suffered considerable damage and only survives in a few places. Large sections of it were demolished and built over, rendering it difficult to determine the exact ground plan, though excavations have yielded an overall impression of its course. It is clear that the wall consisted of straight sections forming an oval outline, and was equipped with towers, two main entrances to the east and west, and smaller gates. The east gate is located at the crossroads between Canevaro Street and Daskalogiannis Street, and the west off Syntrivani (Fountain) Square. Both gates were flanked by square towers. In the mid-13th century Chania fell into the hands of the Venetians, whose main priority was to defend and protect the city. To that end, from 1538 to 1549 an engineer named Michele Sammichieli was appointed to oversee the construction of new walls. The new fortifications, which also surrounded the port area, included a four-sided wall fortified by a moat, a counterscarp, heart-shaped bastions and ramparts. The main castle gate was the so-called Rethemniotiki Porta (Porta Retimiotta), to the south