Здесь же, на берегу, Нестор поведал Телемаху, что после взятия Трои Менелай и Агамемнон повздорили, греческий флот разделился на две части, а Улисс откололся от всех со своими двенадцатью кораблями, и с тех пор его никто не видел. Корабли самого Нестора, вместе с отрядом царя Менелая, благополучно пересекли просторы Эгейского моря. Нестор затем продолжал путь прямо в Пилос, пользуясь попутным ветром, который ни разу ему не изменил. Он слышал, что отряды с Крита, из Мелибеи и Фессалии также благополучно вернулись домой. Что же до Агамемнона, то он по возвращении в Микены был убит возлюбленным своей жены, а царь Менелай — с ним Нестор расстался у мыса Сунион — был настигнут у Малеи бурей, отбросившей половину его кораблей к Криту. Остальные суда пристали к берегу в Египте, и после долгих скитаний «между народов иного языка» Менелай недавно вернулся в свой дворец в Спарте. Возможно, предположил Нестор, Менелай во время своих странствий что-то слышал об Улиссе; и правитель Пилоса посоветовал Телемаху посетить царя Спарты. Для этого он предоставил ему колесницу и назначил в провожатые Писистрата, чтобы тот представил Телемаха Менелаю. Пока же гостю было предложено остаться на ночлег во дворце, ибо, сказал Нестор: «Можно ль, чтоб сын столь великого мужа, чтоб сын Одиссеев выбрал себе корабельную палубу спальней, пока я жив и мои сыновья обитают со мной под одной кровлей, чтоб всех, кто пожалует к нам, угощать дружелюбно?» С этими словами царь пошел «впереди сыновей и зятьев благородных в дом свой, богато украшенный».
Дорога, по которой они шли, очевидно, поднималась по крутым склонам к ровной площадке среди оливковых деревьев, где три тысячи лет спустя Блеген производил свои раскопки. Здесь предшественники Нестора построили дворец, избрав место более безопасное, нежели казавшийся весьма подходящим для царской резиденции мыс, где потерпел неудачу в своих поисках Шлиман. Приведя молодого гостя в свой дом, Нестор вручил ему кубок с выдержанным вином, как говорит Гомер, «чрез одиннадцать лет налитым ключницей, снявшей впервые с заветной той амфоры кровлю». После того «каждый к себе возвратился, о ложе и сне помышляя». Сам Нестор удалился «во внутренний царского дома покой», указав Телемаху «в звонко-пространном покое кровать… прорезную». Встав на другое утро с постели, царь сел на белой мраморной скамье перед высокой дверью дворца, где происходил дневной прием. Вызвав своих шестерых сыновей, он послал одного из них на берег за членами команда Телемаха. Другому сыну царь сказал, чтобы он отправился в поле и велел пастуху пригнать ко дворцу телку. Третий сын должен был сходить за золотых дел мастером Лаэркосом, чтобы тот пришел со своим инструментом и оковал золотом рога телки, предназначенной для жертвоприношения. Тем временем придворным надлежало приготовить все для пира — принести дрова и воду, расставить стулья.
Все это, по словам Гомера, было быстро исполнено. Явился золотых дел мастер с молотом, наковальней и клещами «драгоценной отделки». Получив от Нестора золотой слиток из царской сокровищницы, Лаэркос расплющил его и оковал рога. Один из сыновей царя, Аретос, вынес из дома короб с ячменем, телку вывели туда, где с топором наготове стоял еще один сын Нестора, Фрасимед; Персей держал в руках чашу, чтобы собрать в нее жертвенную кровь. Телку осыпали ячменем и, прочтя молитву, зарезали. Разделав тушу, часть мяса бросили в огонь, остальное поджарили на вертелах и съели.
Тем временем младшая дочь Нестора, Поликаста, отвела Телемаха в баню, омыла его и натерла елеем. Надев чистый хитон и богатую хламиду, Телемах — нарядный, «богу лицом лучезарным подобный» — занял место рядом с Нестором за пиршественным столом. Когда кончилась трапеза, царь возвестил, что пора Телемаху отправляться в путь к Менелаю. Запрягли в колесницу двух коней; ключница снабдила путников в дорогу хлебом, вином и различной пищей, Писистрат взялся за вожжи, и кони помчали колесницу вперед, в столицу Менелая.