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