Вскоре опять дал Эврисфей поручение Гераклу. Он должен был очистить от навоза весь скотный двор царя Элиды, сына лучезарного Гелиоса – Авгия. Бог солнца дал своему сыну неисчислимые богатства. Особенно многочисленны были стада Авгия. Среди его стад были триста быков с белыми, как снег, ногами, двести быков были красные, как сидонский пурпур, двенадцать быков, посвящённые богу Гелиосу, были белые, как лебеди, а один бык, отличавшийся необыкновенной красотой, сиял, подобно звезде. Геракл предложил Авгию очистить в один день весь его громадный скотный двор, если он согласится отдать ему десятую часть своих стад. Согласился Авгий. Ему казалось невозможным выполнить такую работу в один день. Геракл сломал с двух противоположных сторон стену, окружавшую скотный двор, и отвёл в него воду двух рек, Алфея и Пенея. Вода этих рек в один день унесла весь навоз со скотного двора, а Геракл опять сложил стены. Когда герой пришёл к Авгию требовать награды, то не отдал ему гордый царь обещанной десятой части стад, и пришлось ни с чем вернуться в Тиринф Гераклу.

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

Отомстил Геракл и всем союзникам Авгия. Особенно же поплатился царь Пилоса Нелей. Геракл, придя с войском к Пилосу, взял город и убил Нелея и одиннадцать его сыновей. Не спасся и сын Нелея Периклимен, которому дал властитель моря Посейдон дар обращаться в льва, змею и пчелу. Убил его Геракл, когда, обратившись в пчелу, сел Периклимен на одну из лошадей, запряжённых в колесницу Геракла. Один лишь сын Нелея Нестор остался в живых. Впоследствии прославился Нестор среди греков своими подвигами и своей великой мудростью.