Messenien wurde in der prähistorischen Zeit besiedelt und bereits in der Jungsteinzeit bekam es ein stets begehrtes Ziel vieler Eroberer, aufgrund seiner fruchtbaren, weiten Ebenen. Die Ruinen des mykenischen Palasts des legendären Königs Nestor, welcher auch in Epen von Homer erwähnt wurde, findet sich in der Nähe der Hauptstadt. Die Ansiedelung dorischer Stämme beendeten die mykenische Ära.

Die Spartaner fielen zwischen dem 8. - 5. Jahrhundert v. Chr. ein und versklavten Messenien. Die Thebaner befreiten es 369 v. Chr., bevor es erneut 183 v. Chr. unter Römische Herrschaft fiel.

Nach der byzantinischen Epoche siedelten sich die Franken in Messenien an und übergaben das Gebiet 1498 in die Hände der Türken. Gregorios Papaflessas ließ am 23. März 1821 die Revolution gegen die türkischen Belagerer ausrufen, nachdem die türkisch-ägyptische Armee von Ibrahim große Verwüstungen angerichtet hatte. Die Schlacht von Navarino (20. Oktober 1827) führte schließlich zur Freiheit des Peloponnes und zur Gründung des neuen griechischen Staates.