Οι πληροφορίες που έχουμε για τον πόλεμο αυτό είναι πολύ συγκεχυμένες και αγγίζουν τα όρια του μύθου. Και αυτές οι ημερομηνίες της έναρξης και του τέλους του πολέμου είναι αμφίβολες. Το σίγουρο είναι ότι ο πόλεμος κράτησε 17 χρόνια και διαδραματίστηκε το δεύτερο μισό του 7ου αιώνα.

Σαράντα χρόνια περίπου μετά τον Α' Μεσσηνιακό Πόλεμο φαίνεται ότι οι Μεσσήνιοι επαναστάτησαν. Μεταξύ των επαναστατών ήταν και ο Αριστομένης, μια ηρωική μορφή που πήρε διαστάσεις θρύλου. Κατά την έναρξη και το πρώτο έτος του πολέμου η αναμέτρηση των δύο αντιπάλων έγινε στις Δέρες (άγνωστη πόλη ή τοποθεσία). Η πρώτη αναμέτρηση δεν ανέδειξε νικητή, παρόλο που ο Αριστομένης έκανε κατορθώματα αφύσικα για έναν άνθρωπο. Γι' αυτό τον λόγο οι Μεσσήνιοι τον έκαναν βασιλιά, τίτλο που αποποιήθηκε και γι' αυτό τον διόρισαν στρατηγό αυτοκράτορα, δηλαδή στρατηγό με απεριόριστες εξουσίες. Ο Αριστομένης εφάρμοσε μια τακτική καταδρομικών επιχειρήσεων εναντίον της λακωνικής γης με σκοπό να τρομοκρατεί τους κατοίκους της.