The Byzantine army led by Nicephorus Phocas (961-1204 AD) built a new enceinte on top of the stone foundations and remains of the Arab fortress, extending it along a boundary now demarcated by Chandakos, Daedalou and Doukos Beaufort Streets and the Venetian harbour.

The Byzantine walls consisted of what were mostly rectangular towers linked by perpendicular crenellated curtain walls. On the seaward side up to the port, the wall had battlements alternating with towers, while breakwaters at the base afforded protection from the force of the waves.

The enceinte was further furnished with four gates: the Castle or Tax Gate on the south side of the town (at the top end of what is now 25th August Street), the Mole Gate by the harbour, the Royal (lit. "Beautiful") Gate to the east and the Jew Gate to the west, towards Dermatas Bay.