The earliest inhabitants of Messenia are thought by the Greeks of the Classical period to have been 'Pelasgians', as in other regions of Greece.

Supposedly, the Hellenic tribes had then arrived in Greece, and Messenia was settled by Aeolian Greeks.

The Homeric poems suggest that during the Mycenaean period, eastern Messenia was under the rule of Menelaus of Sparta, while the western coast is under the Neleids of Pylos; after Menelaus’s death the Neleids pushed the frontier as far as Taygetus.

The Mycenaean city of Pylos almost certainly lay in Triphylia, and not at the site in Messenia, which in historic times bore that name.

Excavations at Pylos and Nichoria have revealed for Messenia's late Bronze Age (1300s BCE) a bureaucratic, agricultural kingdom ruled by the wanax at Pylos.

The Messenians spoke Mycenaean Greek, and worshipped the Greek gods at local shrines like that at Sphagianes.

During the legendary Dorian invasion of the Peloponnese during the Greek Dark ages, Messenia was supposedly invaded by Dorians under Cresphontes, arriving from Arcadia.

They took as their capital Stenyclarus in the northern plain, and then extended, first their suzerainty, and then their rule over the whole district.During the Archaic period, the relative wealth of Messenia in fertile soil and favorable climate attracts the neighboring Spartans.