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

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

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