Palaiokastro stands on the rocky peninsula of Koryphasio, at the north edge of Navarino bay. A settlement was likely established here in geometric and archaic times, following the abandonment of the mycenaean palace at Ano Englianos. The medieval castle, was built in part on top of ancient fortification ruins. It was founded, according to the Chronicle of the Morea, by the baron of Thebes, husband of Guillaume II de Villehardouin’s widow, Nikolas II de Saint Omer, possibly in 1282-1289. In medieval times it was known as Port-de-Jonc or Avarinos. After the construction of the fortress of Pylos (Niokastro) in the late 16th century, it is referred to as Palaiokastro or Palaio (old) Navarino.

With the weakening of the Frankish presence, it came under Venetian rule and it was conquered by the Ottomans in 1500. It consists of two baileys, separated by a cross wall. The walls are interrupted by square and round towers; some of the battlements have partly survived. The main entrance gate of the south bailey, covered by pointed arches, was opened at the ground floor of a square bastion. Ruins of several buildings survive inside the castle (the commander’s residence, a public bakery , churches, public cisterns and wells etc.).