Setelah kembali ke Yunani, Herakles menyerang AugeasAugeias, raja Elis, dengan membawa pasukan dari Tyrins. Sebelumnya, AugeasAugeias telah mengingkari janjinya untuk membayar Herakles atas bantuannya dalam membersihkan kandang kuda sang raja. Akan tetapi, pasukan Herakles mengalami kekalahan dari para sekutu raja AugeasAugeias, yaitu Amarinkeus dan Moliones, dua putra kembar Aktor. Herakles kalah dalam pertempuran itu karena dia sedang sakit. Saudara tiri Herakles, Ifikles, mungkin terbunuh dalam pertempuranini atau mati dalam perang melawan Sparta.
Herakles kembali ke Tyrins untuk mengumpulkanpasukanbarumengumpulkan pasukanbaru, namun dia diusir oleh Euristheus karena Euristhesu mengira bahwa Herakles mengumpulkan pasukan untuk melawannya. Herakles lalu bermukim di Pheneus, Arkadia. Di kemudian hari, dalam Pesta Olahraga Isthmos, Herakles menangkap dan membuh Moliones. Herakles kembali membangun pasukan di Arkadia dan menyerang AugeasAugeias lagi. Tanpa sekutunya, kerajaan AugeasAugeias kalah dan dia sendiri terbunuh. Herakles kemudian menetapkan putra AugeasAugeias yang dikucilkan, Fileus, sebagai raja Elis. Berdasarkan Apollodoros, Herakles juga dikatakan mendirikan Olimpiade, meskipun pada umumnya orang menganggap bahwa pendirinya adalah HerakelsHerakles dari Gunung Ida, Kreta. Herakles mendirikan mazbah untuk para dewa Olimpus, serta satu mazbah kecil untuk pelops, kakek buyutnya.
----
[[Berkas:Hercules-and-telephus.jpg|200px|thumb|right|Herakles dan bayi Telefos, yang sedang menyusu pada seekor kijang betina.]]
