The Koryphasio Peninsula is rich in archaeological remains, testifying to human presence since the 3rd millennium BCE. In 425 BCE, the Athenians, at the urging of Demosthenes, fortified the most vulnerable parts of the hill, transforming it into a military base. The city that was subsequently established remained active during the Hellenistic and Roman periods.

Thus, the Frankish castle was built atop the foundations of the ancient fortifications. Its security quickly attracted people, leading to the formation of a small settlement outside its walls. In 1423, the castle was sold to the Venetians, who ruled it until 1500. During this period, specifically between 1440 and 1490 (according to the results of radiocarbon dating of the tower shutterings), a second, larger enclosure was constructed to the south, protecting the settlement that had already developed in this area.

In 1500, when Sultan Bayezid II captured Methoni and Koroni, the primary Venetian possessions in the Peloponnese, the castle surrendered to the Ottomans without resistance. In 1572, it came under siege by General Don Juan of Austria, but he failed to capture it. In response, the Ottomans constructed a new fortress, Niokastro, two years later to secure the southern mouth of the Gulf of Navarino. This development led to a decline in the strategic significance of Palaio Navarino, prompting the population to gradually move towards the new fortress. In 1686, the castle returned to Venetian control but was recaptured by the Ottomans in 1715, along with the rest of the Peloponnese.

In 1821, at the outset of the Greek Revolution, Greek forces conquered the castle and used it as a base for their military operations. However, in 1825, they surrendered it to Ibrahim Pasha. After the decisive naval Battle of Navarino in October 1827, the castle ultimately came under the control of the revolutionary Greeks.