The first castle on the spot was built by Byzantine emperor Justinian I after the catastrophic earthquake of 551, re-using building material from pre-Christian structures.

It is known as the "Patrinella", a maiden who is supposed to have been transformed into a man during Ottoman times, guards the city against disease and weeps whenever a prominent citizen of Patras dies.

In particular, the successful repulsion of a great siege of 805 AD by the Arabs and the Slavs was attributed to the city's patron saint, St Andrew.

The Latin Archbishop remained in possession of the castle until 1430, when it was taken by the Despot of the Morea and future last Byzantine emperor, Constantine Palaiologos, who made extensive repairs to its walls.

The Venetians took the castle in 1687 during the Morean War, and kept it until the Morea was retaken by the Turks in 1715, who called it Balya Badra (from Greek Παλιά Πάτρα, 'Old Patras').