Το Παλαιόκαστρο ή Κάστρο του Πετροχωρίου ή Κάστρο της Γιάλοβας σήμερα, ή Κάστρο του Ναυαρίνου, Ναβαρίνου ή Αβαρίνου, όπως λεγόταν αρχικά υψώνεται στην κορυφή του λόφου της χερσονήσου του Κορυφασίου, στη βόρεια είσοδο του Κόλπου του Ναβαρίνου ή Κόλπου της Πύλου έχοντας, σύμφωνα με τον λογοτέχνη Κώστα Ουράνη «μια θέα εξαίσιας γαλήνης και φωτεινής απεραντοσύνης» προς την ευρύτερη περιοχή. Το κάστρο βρίσκεται στην περιοχή της Αρχαίας Πύλου, βορειοδυτικά από την πόλη της σημερινής Πύλου, στην οποία βρίσκεται το άλλο κάστρο της περιοχής, το Νιόκαστρο Ναυαρίνου.
Η ιστορία του ξεκινά από τους πρώτους ιστορικούς χρόνους, όταν το ύψωμα, όπου σήμερα βρίσκεται το φράγκικο κάστρο βρισκόταν η αρχαία κλασική Ακρόπολη της Πύλου. Οι Φράγκοι που κατασκεύασαν στη θέση της ακρόπολης το κάστρο τους, το ονόμαζαν Port de Junch, δηλαδή λιμάνι των σχοίνων. Κτίστηκε το 1278 από τον Φλαμανδό σταυροφόρο Νικόλαο B΄ Σαιντ-Ομέρ.
Το Παλαιόκαστρο ή Παλιοναβαρίνο είναι ένα από τα σημαντικότερα φρούρια που ορθώθηκε επί φραγκοκρατίας στο Μοριά, πάνω στα ερείπια της πρώτης ακρόπολης της αρχαίας Πύλου. Πρόκειται για το παλαιότερο καστέλι του Ναβαρίνου, ονομασία με την οποία λεγόταν η Πύλος στα χρόνια του Μεσαίωνα, καμωμένο και με δομικά υλικά της προγενέστερης ακρόπολης, από τους Φράγκους σταυροφόρους ιππότες. Κατά την διάρκεια της ιστορίας του το κάστρο δέχθηκε πολλές επιθέσεις και άλλαξε πολλούς ηγεμόνες -λόγω της στρατηγικής σημασίας της θέσης του- και υπέστη επίσης και άλλες σημαντικές δομικές επεμβάσεις, τροποποιήσεις χρήσεων και αρχιτεκτονικές μεταβολές, από τους κατά καιρούς κατακτητές, που αλλοίωσαν την αρχική φυσιογνωμία του.
Στη θέση του σημερινού φράγκικου κάστρου βρισκόταν ο πανάρχαιος οικισμός και η ακρόπολη της Πύλου της κλασικής αρχαιότητας που έπαιξε σημαντικό ρόλο κατά τον Πελοποννησιακό πόλεμο. Σύμφωνα με τον καθηγητή Αρχαιολογίας του Πανεπιστημίου Αθηνών Γεώργιο Σ. Kορρέ που πραγματοποίησε ανασκαφές στην ευρύτερη περιοχή αυτή ερευνήθηκαν ίχνη κατοίκησης οικισμού της πρωτοελλαδικής εποχής (3η χιλιετία π.X.), και δύο μεσοελλαδικοί τύμβοι (γύρω στο 2.000 π.X.).
Στο λόφο του Παλαιόκαστρου βρίσκεται και το σπήλαιο του Νέστορος ή του Νηλέως.Κατά την παράδοση, το σπήλαιο χρησίμευσε ως στάβλος για τα κοπάδια αγελάδων του Νηλέως και του Νέστορος.
