Ο πρώτος άθλος που ανετέθη στον Ηρακλή από τον Ευρυσθέα ήταν να του φέρει το δέρμα του λιονταριού της Νεμέας. Αυτό ήταν παιδί του Τυφώνα, ή κατ' άλλους του σκύλου Όρθρου και της Χίμαιρας, στην περιοχή της Νεμέας και ήταν άτρωτο.
Μία άλλη εκδοχή ήταν ότι το γέννησε η Σελήνη, με φρίκη όμως, το πέταξε στη γη, στο όρος Τρητό της Νεμέας, για να τιμωρήσει τον λαό της, επειδή δεν της πρόσφεραν κάποιες θυσίες.
Κατ’ άλλους, η Σελήνη δημιούργησε το λιοντάρι κατ' εντολή της Ήρας από τον αφρό της θάλασσας, και ύστερα κλείνοντάς το σε ένα μεγάλο κιβώτιο, το πήγε η Ίρις στη Νεμέα, δεμένο στην ζώνη της.
Πηγαίνοντας στην Νεμέα, έφτασε στις Κλεωνές, ένα χωριό κοντά στο Άργος και φιλοξενήθηκε από τον Μόλορχο, ο γιος του οποίου είχε σκοτωθεί από το λιοντάρι. Όταν αυτός θέλησε να θυσιάσει ένα κριάρι στην Ήρα, του είπε να περιμένει για τριάντα ημέρες και αν επιστρέψει σώος, να θυσιάσει στον Δία Σωτήρα, ενώ αν πεθάνει, να εκτελέσει θυσίες σαν σε ήρωα.
Φτάνοντας στην Νεμέα βρήκε το λιοντάρι και πρώτα του έριξε με το τόξο. Όταν είδε ότι είναι άτρωτο, το κυνήγησε με το σπαθί του, το οποίο, όμως, στράβωσε και έπειτα, το κυνήγησε με το ρόπαλο. Εκείνο έφυγε και κρύφτηκε στην σπηλιά του, η οποία είχε δύο εισόδους. Ο Ηρακλής έφραξε το ένα στόμιο και από την άλλη επιτέθηκε στο θηρίο, βάζοντας το χέρι του στο λαιμό του και σφίγγοντας τον λαιμό του, το έπνιξε. Σύμφωνα με κάποιες μαρτυρίες, το λιοντάρι του έκοψε και ένα δάχτυλο στην πάλη τους. Μετά το έριξε στους ώμους και γύρισε στις Κλεωνές.
Είχε λείψει κοντά τριάντα ημέρες και ο Μόλορχος ετοιμαζόταν να θυσιάσει το σφάγιο στον ήρωα Ηρακλή, αλλά τελικά το θυσίασε στον Δία Σωτήρα. Ο Ηρακλής τότε έκανε κάποιες αλλαγές στην τέλεση των γιορτών που λέγοντας Νέμεα, και ενώ μέχρι τότε τιμούσαν τον Οφέλτη, έκτοτε τιμούσαν τον Νέμειο Δία.
Ο Ευρυσθέας τρομοκρατήθηκε από την θέα του νεκρού λιονταριού όταν το πήγε στις Μυκήνες και έκτοτε του είπε να δείχνει τους άθλους του από τις πύλες, ενώ έχτισε και ένα χάλκινο πιθάρι κάτω από τη γη για να κρύβεται, και τις εντολές του τις έστελνε στον Ηρακλή με τον κήρυκα Κοπρέα, γιο του Ηλείου Πέλοπα. Ο Ηρακλής έγδαρε το λιοντάρι χρησιμοποιώντας τα νύχια του θηρίου, γιατί ήταν το μόνο υλικό που μπορούσε να κόψει το σκληρόπετσο τομάρι του. Έκτοτε, φορούσε το δέρμα του για πανοπλία και το κεφάλι του για κράνος.
