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