Ο Νέστορας στα νεανικά του χρόνια είχε κάνει πολλά ανδραγαθήματα. Αναφέρετε ότι έλαβε μέρος στον πόλεμο Κενταύρων & Λαπίθων, στο κυνήγι του Καλιδώνιου Κάπρου και στην Αργοναυτική εκστρατεία.
Όταν ο Ηρακλής κατέλαβε την Πύλο ο μόνος από τους 12 γιους του Νηλέα που είχε απομείνει ήταν ο Νέστορας. Αυτός είτε έλλειπε από την πόλη εκείνη την περίοδο, είτε ήταν πολύ μικρός για να αναλάβει στρατιωτικά καθήκοντα. Κατά μια άλλη εκδοχή όταν ο Ηρακλής υπέταξε την Πύλο εγκατέστησε το Νέστορα βασιλιά στο θρόνο του πατέρα του επειδή μόνο αυτός είχε πάρει το μέρος του όταν παλαιότερα είχε ζητήσει από το Νηλέα εξαγνισμό.
Ο Νέστορας παντρεύτηκε την Ευρυδίκη, την κόρη του βασιλιά του Ορχομενού Κλύμενου και έκανε 7 γιους, τον Περσέα, τον Στρατίο, τον Άρητο, τον Εχέφρων, τον Πεισίστρατο, τον Αντίλοχο, και τον Θρασυμήδη και δύο κόρες, την Πεισιδίκη και την Πολυκάστη. Όταν σκοτώθηκε ο Αφαρέας και οι γιοί του από τους Διόσκουρους, τότε ο Νέστορας κληρονόμησε και το βασίλειο της υπόλοιπης Μεσσηνίας.
