Το Παλαιόκαστρo ή Παλιοναβαρίνο, βρίσκεται σε ύψωμα του Κορυφασίου ακρωτηρίου στο βόρειο άκρο του κόλπου του Ναυαρίνου, απέναντι από το βόρειο άκρο της ιστορικής νήσου Σφακτηρίας.
Το κάστρο βρίσκεται σε ύψωμα που δεσπόζει πάνω από την πολυφωτογραφημένη παραλία της Βοϊδοκοιλιάς και τη λιμνοθάλασσα του Διβαρίου (ή «Γιάλοβα»). Η θέση του κάστρου ελέγχει τη βόρεια είσοδο του όρμου του Ναβαρίνου και το εκεί λιμάνι, στη λιμνοθάλασσα της περιοχής Διβάρι.
Το φράγκικο όνομα του κάστρου ήταν “Port de Jonc” που σημαίνει «Λιμάνι των Βούρλων», προφανώς από τα βούρλα που φύονταν σε αφθονία στο αμμώδες έδαφος γύρω από τη λιμνοθάλασσα. Το «Αβαρίνο» οι Τούρκοι το έλεγαν «Αναβαρίν» και μάλλον έτσι προέκυψε το «Ναβαρίνο». Όταν τον 16ο αιώνα οι Τούρκοι έκτισαν το καινούργιο κάστρο της Πύλου (το Νιόκαστρο, από την άλλη μεριά του κόλπου) το φράγκικο κάστρο έχασε την αίγλη του και κατάντησε «Παλιόκαστρο» και «Παλιοναβαρίνο». Στη θέση του κάστρου βρισκόταν πανάρχαιος οικισμός και η ακρόπολη της Πύλου της κλασικής αρχαιότητας που έπαιξε σημαντικό ρόλο κατά τον Πελοποννησιακό πόλεμο. Το μεσαιωνικό κάστρο χτίστηκε στα τέλη του 13ου αιώνα από τους Φράγκους, πάνω στα ερείπια της αρχαίας οχύρωσης. Το κάστρο έχει υποστεί αναρίθμητες προσθήκες και τροποποιήσεις στο πέρασμα των αιώνων. Έχει σχήμα τραπεζοειδές και καταλαμβάνει έκταση 50 περίπου στρεμμάτων.
Η μεγαλύτερη διάστασή του είναι περί τα 200 μέτρα. Τα τείχη και οι πύργοι διατηρούνται σε πολλά σημεία (με την έννοια ότι είναι ακόμα όρθια) αλλά στο εσωτερικό υπάρχουν μόνο ερείπια. Στο εσωτερικό το κάστρο χωρίζεται από ένα εγκάρσιο τείχος σε δύο μέρη (βόρειο και νότιο). Στο βόρειο τμήμα, στην κορυφή, υπήρχε μάλλον η αρχαία ακρόπολη και το παλάτι του Σαιντ Ομέρ.
Εκεί πρέπει να περιοριζόταν και το αρχικό φράγκικο κάστρο. Στους χρόνους πριν από τη Φραγκοκρατία πρέπει να ανήκει ένας μικρός ορθογώνιος πύργος στο δυτικό άκρο του δυτικού εξωτερικού τείχους, που είναι κτισμένος με το πλινθοπερίκλειστο σύστημα δομής των βυζαντινών χρόνων.
Εντός των τειχών συναντά κανείς ερείπια των δημόσιων και ιδιωτικών κτηρίων, της καθολικής εκκλησίας και υπόγειων δεξαμενών νερού. Το μεγάλο πρόβλημα του κάστρου ήταν ανέκαθεν το νερό, καθώς δεν υπάρχει καμιά πηγή νερού στο βράχο. Κάτω από τα τείχη του κάστρου υπάρχει η λεγόμενη «σπηλιά του Νέστορα» που αναφέρει ο Παυσανίας, η οποία συγκοινωνεί απευθείας με το Παλαιόκαστρο. Στη σπηλιά αυτή, σύμφωνα με το μύθο, έκρυψε ο Ερμής τις αγελάδες που είχε κλέψει από τον Απόλλωνα. Το σπήλαιο αυτό εξερεύνησε πρώτος ο Ερρίκος Σλήμαν το 1874.