При правлении сыновей Махаона или поколением спустя состоялся поход Гераклидов на Пелопоннес, и потомки Нелея были изгнаны из Мессении. О потомках Асклепия ничего не говорится. Поскольку Асклепий считался помощником Геракла, который излечил его от раны, вероятно, сыновья и внуки Махаона не были затронуты нашествием Гераклидов и правили в своих городах (вероятно, в Герении и Ферах). Павсаний подчеркивает: когда правление Мессенией досталось Гераклиду Кресфонту, древние мессеняне не были изгнаны, а лишь уступили часть своей земли дорянам. Именно поэтому Кресфонту пришлось построить собственную столицу – Стениклеру.

При внешне мирном покорении Мессении, правление Кресфонта, видимо, не было безоблачным. Он и его сыновья погибли в результате заговора. Выжил лишь младший Эпит, который находился у своего деда, царя Аркадии Кипсела, на воспитании (дочь Кипсела Меропа была женой Кресфонта). О том, что в заговоре участвовала мессенская знать, говорит тот факт, что утверждению у власти Эпита помогли дорийские цари и их союзники – аркадяне. После расправы над заговорщиками Эпит постарался сделать свое правление мягким, и его потомки стали называться Эпитидами, а не Гераклидами. Еще больше постарался заслужить уважение Главк, сын Эпита, который возродил поклонение Зевсу на горе Итоме, где священный участок основали еще Поликаон и Мессена. Также он первым принес священные дары Махаону и установил культ Мессены. Сын Главка Истмий добавил к этому святилище в Ферах в честь сыновей Махаона Горгаса и Никомаха. Сын Истмия Дотад построил пристань в Мофоне. Его сын Сибота ввел жертвы реке Памису и Эвриту, сыну Менелая, – из уважения к династии, правившей в Эхалии. При Финте, сыне Сибота, были установлены связи Мессении и священного острова Делоса, где находилось особо почитаемое святилище Аполлона. С Финта начинается распря с лакедемонянами – первоначально из-за святилища Артемиды Лимнатиды на границе двух земель.

Необходимо обратить внимание, что именно в Мессении культ Геракла Фиванского приобрел особый размах. И в дальнейшем связи с Беотией у мессенцев были самые основательные. Напротив, Спарта тяготела к Криту – дочь Икария Меда вышла замуж за критского царя Идоменея, участника Троянской войны. Другая его дочь Пенелопа вышла замуж за Одиссея, царя Итаки, который в течение многих лет был сподвижником Идоменея, участником междоусобиц на Крите.

Мессения меньше всего пострадала от Гераклидов, и здесь расселение дорийцев было, видимо, совсем незначительным. Коренное население сохранило свою знать, его города не были подвергнуты разграблению. Тем не менее, дорийцы считали себя хозяевами, а коренное население – подчиненным. Когда выяснилось, что подчиненная роль мессенцами не принимается, разгорелась война.

Предпочитая в других случаях описывать достопримечательности и элементы культа, в Мессении Павсаний подробным образом передает историю этого края – мучения мессенцев, видимо, ставшие своего рода иллюстрацией ко всей истории Пелопоннеса.

Повод к Первой Мессенской войне (743-724 гг. до н.э.) был следующий. Лакедемоняне утверждали, что мессеняне совершили насилие над их девушками во время праздника, а царя Телекла, который пытался остановить насилие, убили. Версия мессенян – что в девушек были переодеты юноши с кинжалами, которые напали на мессенскую знать, и инициатором заговора был Телекл, намеренный захватить Мессению. Аргументом мессенян было отсутствие требований компенсации за убийство Телекла со стороны лакедемонян. Что должно было подтверждать: о заговоре в Лаконии были известно. Но почему же тогда Спарта тут же не начала войну? Если она готовилась к захвату Мессении, то убийство царя было бы лучшим поводом для нападения, и поход возглавил бы царь из второй династии, царь-соправитель.

Только в следующем поколении взаимная неприязнь дошла до войны. В это время в Мессении правили сыновья Финта Антиох и Андрокл, а в Лаконии цари Алкамен, сын Телекла, и Феопомп – из второго царствующего дома. Поводом для войны стал конфликт между знатным мессенцем Полихаром, известным как чемпион в 4-й олимпиаде. Он доверил своих коров лаконцу Эвфану, а тот не только продал их, но и убил сына Полихара. Полихар безуспешно пытался найти управу на обидчика у лаконских царей и эфоров, после чего обезумел и начал убивать всякого лакедемонянина, которого встречал. Мессенцы не выдали обезумившего Полихара (потому что не получили для расправы Эвфана), лакедемоняне же отказались решать вопрос в аргивском или афинском суде или в собрании амфиктионов (представительство живущих вокруг народов), и объявили войну (здесь Павсаний входит в противоречие: пишет также, что лакедемоняне не послали вестника с объявлением войны).

Положение Мессении усугубилось внутренней распрей. При обсуждении на народном собрании Андрокл высказался за то, чтобы выдать Полихара как убийцу, а Антилох предложил представить, как того будут пытать на глазах Эвфана. Спор дошел до вооруженной схватки, в которой Андрокл и его окружение было перебито. Попытка Антилоха предложить лакедемонянам судебное разбирательство не была удостоена ответа. Сам Антилох через несколько месяцев умер, а царство принял его сын Эвфай, которому и пришлось вести войну с могущественным соседом.

Первым актом войны был захват лакедемонянами приграничного городка Амфеи, который располагался на удобном для обороны холме, но беспечно оставил ворота открытыми и без охраны. Ночью лекедемоняне овладели городом, перебив тех, кто попытался оказать сопротивление. Павсаний датирует это событие вторым годом 9-й олимпиады.

Три года противостоящие стороны обменивались набегами и уводом скота. Города мессенцев хорошо охранялись, спартанское войско не могло их взять и быстро оставило эти попытки. На четвертый год Эвфай объявил поход, ему навстречу двинулось войско лакедемонян. Эвфай вывел войска к глубокому оврагу, с другой стороны подошло войско из Лакедемона. Овраг не позволил тяжеловооруженной пехоте сойтись в схватке, а легкая пехота и конница переходили через овраг и беспорядочно сталкивались с противником. Ночью Эвфай укрепил свой лагерь со всех сторон кольями, и наутро лакедемоняне убедились в невозможности продолжать сражение без тяжелых потерь. Обе стороны отступили.

На следующий год поход спартанцев возглавили цари Феопомп и Полидор, сын умершего к тому времени царя Алкамена, внук Телекла. Цари стали по флангам, а в центре командовал Еврилеонт родом из Фив, считавший себя дорийцем. Эвфай занял правый фланг мессенского войска напротив Феопомпа.

При многословном описании битвы Павсаний дает очень незначительную информацию о тактике обеих сторон, ограничиваясь замечанием, что лакедемоняне были более организованными и держали строй, а мессеняне проявляли больше отчаянной храбрости. При том что вместе с лакедемонянами в войске были в качестве вспомогательных отрядов представлены присоединенные к Лаконии города, изгнанные аргосцами асинейцы и дриопы и критские лучники, в битве принимали участие исключительно тяжеловооруженные воины. Легкая пехота оставалась в тылу в соответствии с древними обычаями. Это означает, что битва носила скорее ритуально-состязательный характер. Более мощные правофланговые отряды каждой армии одержали победы, но отказались от преследования, чтобы спасти отступающую часть своего войска, а в центре силы оказались равными. Ночь прервала сражение, а наутро обе стороны предпочли перемирие и захоронение погибших.

После битвы, которая не принесла успеха ни одной из сторон, способность мессенян к войне стала быстро падать: денежных средств для содержания гарнизонов не хватало, рабы перебегали к противнику, население поразила болезнь. Вероятно, дорийское население Мессении также сочувствовало Спарте. По этим причинам Эвфай с войском предпочел укрепиться на горе Итоме близ небольшого городка Трикка, упоминаемого еще в "Илиаде". Дельфийский оракул предложил мессенянам для спасения принести человеческую жертву, выбрав по жребию деву из рода Эпита. Но определенная жребием дочь Ликиска была объявлена не родным ему ребенком, и пока мессеняне обсуждали этот вопрос, Ликиск с дочерью бежали в Спарту. Тогда свою дочь предложил в жертву Аристодем. Но ее возлюбленный объявил, что уже обручен с нею, и отец уже не имеет над ней власти, более того, она уже беременна. Пришедший в ярость Аристодем убил свою дочь и, вскрыв чрево, убедился, что плода в нем нет. Ужасное преступление невозможно было объявить жертвой богам, но мессеняне дали царю Эвфаю себя убедить, что в подобном виде жертва будет принята богами.