Το Παλαιόκαστρο υψώνεται επάνω στη βραχώδη χερσόνησο του Κορυφασίου, στο βόρειο άκρο του κόλπου του Ναβαρίνου. Στην ίδια θέση πιθανολογείται ότι αναπτύχθηκε οικισμός, μετά την εγκατάλειψη του μυκηναϊκού ανακτόρου του Άνω Εγκλιανού, ήδη από τους γεωμετρικούς και τους αρχαϊκούς χρόνους. Το μεσαιωνικό κάστρο, που κτίζεται σε πολλά σημεία επάνω σε θεμέλια αρχαίων οχυρώσεων, ιδρύθηκε σύμφωνα με το Χρονικόν του Μορέως από τον διοικητή της βαρωνίας της Θήβας και σύζυγο της χήρας του Γουλιέλμου Β΄ Βιλλεαρδουίνου, Νικόλαο Β΄ de Saint Omer, πιθανότατα στο διάστημα 1282-1289. Στη μεσαιωνική περίοδο ήταν γνωστό ως Port-de-Jonc ή Αβαρίνος, ενώ μετά την ίδρυση του φρουρίου της Πύλου (Νιόκαστρο), στα τέλη του 16ου αιώνα, αναφέρεται ως Παλαιόκαστρο ή Παλαιό Ναβαρίνο.

Με την αποδυνάμωση της φράγκικης παρουσίας περνάει στην κυριαρχία των Ενετών και το 1500 καταλαμβάνεται από τους Οθωμανούς. Αποτελείται από δύο αμυντικούς περιβόλους, οι οποίοι χωρίζονται με εγκάρσιο τείχος. Τα τείχη διακόπτονται από τετράγωνους και ημικυκλικούς πύργους και σε μερικά σημεία σώζουν τις επάλξεις τους. Η κύρια πύλη του νότιου περιβόλου, που καλυπτόταν από οξυκόρυφα τόξα, ανοίγεται στο ισόγειο ορθογώνιου πύργου-πυλώνα. Στο εσωτερικό των περιβόλων σώζονται ερείπια των κτηρίων του οικισμού (οικία του Διοικητή, δημόσιος φούρνος, εκκλησίες, δημόσιες κινστέρνες και πηγάδια κ.τ.λ.).