Euristėjas pirmiausiai liepė Herakliui užmušti Nemėjos liūtą ir atnešti liūto kailį. Heraklis iškeliavo. Nemėjoje jis patykojo liūtą ir taikliai paleido strėlę, tačiau pabaisos nesužeidė. Tada ėmė vytis žvėrį su kuoka, bet liūtas pasislėpė oloje su dviem angom. Vieną angą Heraklis užvertė, o pro kitą įlindo į olą, čiupo liūtą už gerklės ir pasmaugė (pagal kitą versiją, uždusino sukišęs ranką liūtui į nasrus). Jis užsimetė liūtą ant nugaros ir po kurio laiko sugrįžo į Mikėnus.