The old castle/fortress of Paliokastro was built by the Franks around 1278 / 13th (it seems position built on the ruins of a ancient Acropolis from the Pylos-Koryphasion city of Classical period), is situated the north side of Navarino bay, on the top of the hill (this promontory called Koryphasion -or Coryphasion-).
The castle is ruin, but the outside walls and his round and square towers is saved in a good condition.
Paliokastro castle lost his importance when in 1573 the Turks built a new fortress (Neokastro) at the southern entrance of the Navarino bay.
Below the castle, in the cliff just above Voidokilia, you find a cave referred to as Nestor’s cave by ancient Greek traveller Pausanias; according to Greek mythology, it was there that Hermes hid the cattle he had stolen from his brother, Apollo; However, the latter found out and as a penance Hermes offered him a lyre made of tortoise shell.
NB: this text is taken from a presentation page on my website voidokilia.com