Το Νιόκαστρο είναι κτισμένο σε μικρό λόφο που βρίσκεται στη νότια είσοδο του κόλπου του Ναβαρίνου. Ονομάζεται Νιόκαστρο ή Νέο Ναβαρίνο, σε αντιδιαστολή με το Παλιόκαστρο ή Παλαιό Ναβαρίνο (φράγκικο κάστρο του 13ου αιώνα), που καταλαμβάνει το βόρειο άκρο του κόλπου. Ιδρύθηκε από τους Τούρκους το 1573, με στόχο να προστατέψει το φυσικό λιμάνι του Ναβαρίνου και τα νοτιοδυτικά παράλια της Μεσσηνίας και παρέμεινε στην οθωμανική κατοχή έως την έναρξη της Ελληνικής Επανάστασης, με ένα σύντομο διάστημα ενετικής κυριαρχίας από το 1686 έως το 1715. Το 1821 ελευθερώνεται από τους Έλληνες επαναστάτες, αλλά το 1825 καταλαμβάνεται από τον Ιμπραήμ. Ακολουθεί η ναυμαχία του Ναβαρίνου (1827) και το 1828 το κάστρο παραδίδεται στο γαλλικό εκστρατευτικό σώμα του Maison, οπότε επιδιορθώνονται τα τείχη και οι προμαχώνες του. Στο β΄ μισό του 19ου και μέχρι τα μέσα του 20ου αιώνα η ακρόπολη του φρουρίου στέγαζε τις ποινικές φυλακές της Πύλου. Στον Β΄ Παγκόσμιο Πόλεμο, το φρούριο υπήρξε βάση των ιταλο-γερμανικών στρατευμάτων.

Το φρούριο αποτελείται από την εξαγωνική ακρόπολη στα ανατολικά, και τον τειχισμένο οικισμό στα δυτικά. Στο υψηλότερο και πιο ευάλωτο σημείο του κάστρου κτίστηκε η ακρόπολη, η οποία ενισχύθηκε με άνυδρη τάφρο εξωτερικά και έξι πεντάπλευρους προμαχώνες. Τα τείχη που περικλείουν τον οικισμό εξωτερικά διαμορφώνουν σκάρπα, απολήγουν σε επάλξεις, όπου η πρόσβαση επιτυγχάνεται από στενό περίδρομο, και ενισχύονται από δύο ημικυκλικούς προμαχώνες στα νότια και στα βόρεια. Χαρακτηριστικό είναι το τείχος της νότιας πλευράς, η «Μεγάλη Βέργα», όπου ο περίδρομος εδράζεται σε σειρά από ημικυλινδρικές καμάρες. Στα δυτικά, δύο τετράπλευροι προμαχώνες προστατεύουν την είσοδο του λιμανιού. Η είσοδος στο κάστρο γινόταν από την νοτιοανατολική πλευρά, όπου στέκεται η επιβλητική πύλη, η «Ζεματίστρα».