Το Σπήλαιο Νέστορος βρίσκεται στο βορειοανατολικό μέτωπο του λόφου του Παλαιοκάστρου, σε σημείο από το οποίο εποπτεύει τον όρμο της Βοϊδοκοιλιάς, 17 χλμ. περίπου βόρεια της Πύλου Μεσσηνίας. H είσοδός του, σχεδόν τριγωνικού σχήματος και ορατή από μεγάλη απόσταση, οδηγεί σε δύο επιμήκεις προθαλάμους που καταλήγουν στην κύρια αίθουσα του σπηλαίου, διαστάσεων 20 Χ 16 μ., με θολωτή οροφή ύψους περίπου 20 μ. Ενδεχομένως ταυτίζεται με το σπήλαιο, το οποίο ο Παυσανίας (IV, 36, 2) συσχέτισε με τον μύθο του σταυλισμού των κοπαδιών του βασιλιά της Πύλου Νέστορα και πριν από αυτόν του Νηλέα, ο οποίος θεωρείται από την παράδοση ότι τα είχε φέρει από τη Θεσσαλία.



Η ιστορία της έρευνας του σπηλαίου, καθώς και του λόφου του Παλαιοκάστρου, όπου βρίσκονται τα μεσαιωνικά ερείπια του κάστρου του Ναυαρίνου, ξεκινά τον 19ο αιώνα με ανασκαφή, που διεξήχθη από τον Ερρίκο Σλήμαν, ο οποίος αναζήτησε σε αυτές τις θέσεις σημεία της ομηρικής τοπογραφίας του βασιλείου του Νέστορα στην Πυλία. Ολιγοήμερες ανασκαφές διεξήχθησαν σε διάφορες περιόδους του 20ού αιώνα, ανάμεσα στις οποίες η πιο συστηματική ήταν ή έρευνα, που πραγματοποιήθηκε το 1953 από τον William A. McDonald με τη συνεργασία του Δημητρίου Ρ. Θεοχάρη, στο πλαίσιο του προγράμματος ερευνών του Carl W. Blegen του Πανεπιστημίου Cincinnati των ΗΠΑ στο ανάκτορο του Νέστορα στον Άνω Εγκλιανό στη Χώρα. Το 1980 διεξήχθη η πλέον πρόσφατη ανασκαφική έρευνα από τους Γεώργιο Σ. Κορρέ και Αδαμάντιο Σάμψων, στο πλαίσιο των ερευνών του Πανεπιστημίου Αθηνών και της Εν Αθήναις Αρχαιολογικής Εταιρείας στην περιοχή της Βοϊδοκοιλιάς.



Το Σπήλαιο Νέστορος χρησιμοποιήθηκε αρχικά κατά τη Νεολιθική περίοδο, από την οποία προέρχονται ενδιαφέροντα δείγματα διακοσμημένης και ακόσμητης κεραμικής της 6ης και 5ης χιλιετίας π.Χ. Ωστόσο η διατάραξη των επιχώσεων από τις προηγούμενες ανασκαφικές έρευνες, δεν επιτρέπει διαπιστώσεις σχετικά με το κατά πόσο η παρουσία του Νεολιθικού ανθρώπου στο σπήλαιο ήταν συστηματική και επαναλαμβανόμενη και εάν σχετιζόταν αποκλειστικά με αγροτοκτηνοτροφική και αποθηκευτική οικονομία. Η χρήση του σπηλαίου έγινε πιο αποσπασματική κατά την Πρωτοελλαδική περίοδο (3η χιλιετία π.Χ.), αλλά εντάθηκε κατά την ύστερη Μεσοελλαδική και Υστεροελλαδική (Μυκηναϊκή) περίοδο (2η χιλιετία π.Χ.). Από την τελευταία φάση προέρχεται σημαντικός αριθμός από θραύσματα κυλίκων. Έντονη χρήση του σπηλαίου για μικρό διάστημα τεκμαίρεται κατά τη Γεωμετρική περίοδο και πιο αραιή κατά τους Υστεροκλασικούς χρόνους και μετέπειτα χρόνους. Η παρουσία του ανθρώπου στο σπήλαιο κατά τις φάσεις αυτές πρέπει να ερμηνευθεί ως άσκηση λατρείας και να συνδυαστεί με την πλούσια οικιστική και ταφική δραστηριότητα στην ευρύτερη περιοχή της Βοϊδοκοιλιάς.



Το σπήλαιο δεν αποτελεί οργανωμένο αρχαιολογικό χώρο.