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