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