Héraklész negyedik feladata a nemeai oroszlán, a hidra és a sztümfaloszi madarak legyőzése után Artemisz szarvasának elejtése volt. Ennek a szarvasnak arany szarvai és sárgaréz lábai voltak. Artemisz  megbízta, hogy pusztítson a gyümölcsösökben és a mezőkön, hogy így büntesse meg a  halandókat. A vadászat istennője nagyon megharagudott rájuk, mert nem vittek neki elég áldozatot a templomba. A szarvas mindent letaposott,  levágta a gyümölcsöt a fákról.   Héraklész miközben Arkádia sűrű erdei között vándorolt, megtalálta az aranyszarvú szarvas lakhelyét. De amint meglátta, elvesztette szem elől. Nem úgy tűnt számára, mintha futott volna vagy egyáltalán megérintette volna lábaival a földet. Úgy nézett ki, mint egy forgószél, amely végigmegy a síkságon, egy pillanatra megáll, majd újból egy szempillantás alatt eltűnik. Héraklész azonban nem adta fel, mindenhová követte, míg végül meg nem érkezett az addig ismert világ végére, Hiperborea földjére, ahol az isztriai források erednek. Végül egy folyóhoz értek, amelynek neve Ladon volt, ennek túloldalán állt Artemisz temploma. Itt a szarvas menedékre talált, Héraklész nem tudta volna kihozni onnan. De még mielőtt elérte volna  a templom kapuit, egy íjat célzott rá, amely eltalálta az egyik lábát. A sérült állat most megállt, Héraklész pedig gyorsan összekötözte a lábait. Artemisz azonban megjelent előtte és kérdőre vonta őt. Héraklész viszont azt válaszolta neki, hogy Héra utasítására fogja  a vadat Mükéné királyához vinni.

Az ötödik próba az erümanthoszi vadkan elejtése volt, ezt  a vadat is élve kellett elvinnie Eurüsztheusz királyhoz. A vadkan Psophida erdőiben tombolt, amely Arkádia egyik ritkán lakott területe. Séta közben Héraklész találkozott Pholos kentaurral. Ennek a kentaurnak szelíd természete volt, mivel korábban már ismerte a hőst, meghívta őt egy lakomára. Ezalatt Pholos egy hordó bort is megkezdett, amit Dionüszosztól kapott. Így nyilván  ez olyan bor volt, amiből csak az istenek ittak. Aromája annyira erős, hogy betöltötte az egész hegyet megszédítve a környék embereit,  szörnyeit és  vadállatait. A kentaurok felháborodva mentek el, hogy kérdőre vonják Pholost. Botokkal, kövekkel rohamozták meg őket, egyikük nagy sziklát dobott Héraklész homlokára, egy másik pedig keményen megütötte őt egy tölgyfa törzsével. Ha Héraklész nem lett volna olyan erős, azonnal elpusztult volna. Ezt látva Héraklész nekirontott az első kentaurnak, majd ököllel megütötte azt, ezután az összes többit is, amely meg akart vele küzdeni. Hozzákötözte őket  a farönkhöz és bezúzta a koponyájukat. A megmaradtak félve rohantak el a helyszínről, azonban a hidra vérébe mártott nyilak elől ők sem menekülhettek. Megköszönve Pholos-nak a vendéglátást, elindult abba az erdőbe, ahol a vadkan élt. Egy bozótosban talált rá. Fehér agyarai akkorák voltak, mint egy ember, és élesek, mint egy lándzsa. Ezekkel az agyarakkal egy tölgyfát kitépett gyökerestől, majd Héraklész felé dobta. Héraklész gyorsan félreugrott, ekkor első gondolata az volt, hogy felveszi a fatörzset és visszadobja azt a vadkanra. De ekkor eszébe jutott, hogy a fenevadat élve kell elvinnie a királyhoz. A vadkan a völgybe akart volna menekülni, de Héraklész ezt nem engedte, arra kényszerítette, hogy felmásszon az Erümanthosz csúcsára, amelyet hó borított. A vadkan emiatt kifáradt, nehezen tudott futni a hóban és egyre jobban lihegett. Héraklész megütötte a tarkóján, hogy elveszítse eszméletét, ezután a hátára vette és elindult Mükéné felé. Amikor Eurüsztheusz meghallotta a hírt, hogy Héraklész a vadállattal Mükénébe érkezett és éppen belép a város kapuin, kiabálni kezdett a tanácsadókkal, hogy állítsák meg. De senki sem mert az útjába állni Héraklésznek, a király ezúttal nem úszta meg a vele való találkozást. A gyáva király félelmében egy rézhordóba bújt, onnan kiabált: - Öld meg vagy engedd el! Nincs szükségem a vaddisznóra. Ne felejtsd el, hogy a rabszolgám vagy, én pedig ezt parancsolom neked ! Héraklész ekkor így felelt: - Elfogadtam azt, hogy szolgáljalak téged, de nem azért, mert bármit is érsz a szememben. Hagyományunk megköveteli, hogy fizessünk meg minden véres cselekményért egy ideig rabszolgaságban maradva. De tudd,  hogy nem érted dolgozom, hanem azokért, akiket szeretek. Értük mentem el, hogy megszabaduljanak az emberek ettől a fenevadtól! Eurüsztheusz azonban egészen addig nem jött elő a hordóból, amíg meg nem látta a vaddisznót megnyúzva és a húsát egy nyárson. Miután összeszedte a bátorságát, elmondta a következő feladatot: - Elis királyának háromezer ökre van, némelyiknek olyan a lába, mint a hó, mások teljesen fehérek, mint a hattyúk. Vannak lila színűek is köztük, mint a szidóni szövet. A bika, amelynek neve Phaeton, a csillogó aranycsillaghoz hasonlít. Ezekben az istállókban a trágya hegyként magasodik. Szóval menj Augeasz királyhoz és takarítsd ki istállóit! 

Héraklész fogadást kötött Augeasz királlyal, aki  háromszáz ökröt ígért neki annak fényében, ha teljesíteni tudja feladatát egy nap alatt. Miután megérkezett Elada-ba, Héraklész kihajtotta az összes jószágot a mezőre. Árkot ásott, amely a közeli folyónál ért véget.  Ezután két lyukat ütött az istálló falába. A víz behatolt az árokba, közben átfolyt az istállókon is és magával sodort minden trágyát, ami benne volt. Még le sem ment a Nap, mire az istálló teljesen kitisztult és még a falakat is volt idő helyrehozni. A király azonban nem tartotta be ígéretét, ugyanis arra hivatkozott, hogy Héraklész rabszolga, ezért nem köteles neki igazat mondania. Héraklész ekkor így szólt: -Nem mindig leszek rabszolga! Meg fogok később veled küzdeni, amikor szabad leszek már! Ez később így is lett, Augeasz seregei élén vesztett a csatában és ő maga is meghalt.  A hős a csata után háromszáz olajfát ültetett oda, elindítva az első olimpiát a kivívott győzelem tiszteletére, amely a bátor, erős és becsületes emberek tornája lett ezentúl.

Augeasz istállójának takarítása után Héraklész új, sokkal veszélyesebb megbízatást kapott.  Az előző feladat egyszerűbb volt  a többinél, mivel Héra azt hitte, hogy a hős csak az erejét tudja használni. A nehezebb feladatokat későbbre tartogatta, hogy kifárassza őt. Eurüsztheusz így elküldte Hellászból Minósz királyságába, amely Krétán volt, éppen azon a szigeten, ahol apja is megszületett. Az itteni bika Poszeidón tengeristen védelmét élvezte. Nagy pusztítást csinált a szigeten, mindent termést feldúlt.  Acélhuzalokból hálót készített, mint amilyeneket halfogásra használnak. Amikor  a bika lehajtott szarvakkal Héraklész felé indult, belegabalyodott  a hálóba. Minósz király nagyon örült, hogy megszabadította a szigetet ettől a csapástól. Ezután Héraklész felült a bika hátára, amely átúszott  a tengeren. Eurüsztheusz istállóiba börtönözték be végül. De miután elment, Eurüsztheusz elengedte a bikát, ezúttal is hordóban bújt meg mindaddig, amíg az ott tartózkodott. A bika Marathon mellett élt tovább, ahol később majd Thészeusz győzte le.

Miután Héraklész visszatért Krétáról, Eurüsztheusz megkérdezte Hérát, hogy hová küldje. Héra elmondta neki, hogy Trákiában él Arész fia, akit Diomédész-nek hívnak. Istállóiban olyan fekete lovak vannak, amelyek hússal táplálkoznak . Minden külhonit, aki Trákiába megy, Diomédész megetet ezekkel a lovakkal.  Eurüsztheusz hitt abban, hogy ezúttal Héraklész el fog bukni, mivel a király Árész védelmét élvezte és ő segíteni fog neki. Héraklész egy hajóval indult Trákia földjére a tengeren át, de útközben viharba keveredett, ezért megállt  a thesszáliai tengerparton. Itt uralkodott egyik barátja, Admétosz.  Értesült arról, hogy az egész ország gyászol amiatt, mert a király meg fog halni. Thanatos, a halál soha nem megy el üres kézzel. De mivel a Moirák másképp akarták, felajánlotta a királynak azt, hogy kiválthatja életét. Viszont ezt nem érheti el úgy, ha kényszerít erre bárkit is, annak önként kell feláldoznia magát helyette. Egyedül felesége ígérte meg neki, hogy vállalkozik erre. Thanatos aznap éjjel megjelent a király feleségének, Alkésztisznek a szobájában. Kardjával levágott egy tincset a hajából,  Alkésztisz pedig lehunyta szemeit. Amikor Admétosz rátalált felesége kihűlt testére, kiáltásai messzire hallatszottak.  Héraklész tudta, hogy az első éjszaka, miután minden halandó lehunyja a szemét, Thanatos isten visszatér és elviszi a halott test árnyékát. Titokban megbújt azon a helyen, ahol Alkésztisz teste feküdt. A hagyomány szerint senki sem tartózkodhatott a közelben, amikor a halál istenének, Thanatos-nak kellett volna eljönnie. Héraklész egész éjjel birkózott vele, végül reggelre sikerült leterítenie őt és így legyőzte a halált. Csak azután engedte el, hogy megígérte neki visszahozza az életbe Alkésztiszt. Éppen időben, mert Admétosz öngyilkosságra készült. Azonban amikor újból meglátta maga előtt feleségét élve, nyomban eldobta a kést. Héraklész nem maradt sokáig a palotában, folytatnia kellett útját Trákiába. Annak tengerpartján egy nagy sereg várt rá, de sikerült legyőznie őket. Ezután elment az istállókba, láncokkal kötözte meg a lovakat és a hajóhoz vitte őket. Diomédész viszont a parton egy újabb sereggel várta őt. Mivel ez a sereg sokkal nagyobb volt az előzőnél, a harc is tovább tartott. Három nap múlva az életben maradottak elmenekültek, a király azonban Héraklész kezébe került, aki túszként  a hajóra vitte őt. Ott azonban egy alkalommal az éhes lovak darabokra tépték őt. Eurüsztheusz király amikor megtudta, hogy Diomédészt útközben saját lovai ették meg, ismét a hordóba ugrott. Héraklész bezárta a lovakat néhány széles istállóba, de Mükéné királya ismét megparancsolta szolgáinak, hogy nyissák ki nekik a kaput és engedjék szabadon azokat. A lovak őrült rohanásukban elérték az erdőt, amely körülvette az Olümposzt, a legmagasabb hegyet és egyben az istenek lakhelyét. Zeusz feldühödött emiatt, majd  néhány farkast küldött, amelyek sarokba szorították végül a lovakat és széttépték mindegyiket.

A kilencedik próba sokkal nehezebb lett, mint az előzőek. Hippolité amazon királynő övét kellett megszereznie ezúttal, aki a harcos nőkből álló törzs vezetője volt. Héraklész ebben a feladatban segítséget is kapott más hősök által, így együtt indult el Thészeusz-szal, Péleusz-szal és Telamon-nal. Az amazonok földjén azonban nagyon meglepődtek akkor, amikor Hippolité kiment eléjük a tengerpartra és önként felajánlotta nekik az övét. Az égből azonban Héra figyelte őket. Látta, hogy Zeusz fia  ügyes beszédével túl könnyen szerezte meg az övet. Amazonnak álcázta magát, majd beállt közéjük és viszályt szított. Háború következett annak ellenére, hogy Hippolité erre nem adott engedélyt. Amikor Héraklész is belépett a csatába, az amazonok úgy hulltak, mint a learatott  kalászok a földeken  lovaikkal és fegyvereikkel együtt mindenestől. A csatában odaveszett Hippolité is. Hazafelé menet Héraklész Trójában pihent meg, ahol pestis tombolt. Egy víziszörny is pusztította a város lakóit, amelyet Poszeidón küldött rájuk. A trójai uralkodónak azt jósolták, hogy akkor szabadul meg ezektől az átkoktól, ha leányát feláldozza. Hészionét így a part menti sziklákhoz kötözték, hogy a szörny elragadja őt. A leány  megtetszett Héraklésznek, ezért megküzdött a víziszörnnyel.  A szörny megölése után Laomedón király  megtagadta a díj megfizetését, ezért Héraklész azzal távozott, hogy sereggel tér majd vissza. Később ez meg is történt, Heszioné pedig barátja, Telamón felesége lett.

A tizedik feladat során messze a világ végére kellett mennie Héraklésznek. Ez lett volna utolsó próbája, mert eredetileg tízet kellett teljesítenie, de Eurüsztheusz kettőt nem fogadott el. Gerüón bíbor marhacsordáját kellett Mükénébe terelnie onnan, ahol a Nap lenyugszik Afrika nyugati partjainál és elkezdődik a széles óceán. Itt felállította Héraklész oszlopait a szoros partján, amely összekötötte Európát Afrikával. A szigetre érve a marhacsorda éber őrzője, Orthos kétfejű kutya észrevette és megtámadta őt. Héraklész agyonütötte, majd megölte a pásztort is és elhajtotta az állatokat. Gérüón hamarosan utolérte őt, de Héraklész lenyilazta. A visszaút során áthaladt Itálián is. Etruszk nyelven a bika italos, emiatt nevezték el később a félszigetet Italiának. Egy bika azonban átúszott Szicíliába is, sok állat szétszéledt, mert veszettség kínozta azokat. A Mükénébe eljutott teheneket feláldozták. Itt azonban Eurüsztheusz azzal fogadta őt, hogy a hidra legyőzése során nem egyedül oldotta meg a feladatot és Augeasz istállóinál igénybe vette a folyó munkáját, ezért ezek semmisnek minősülnek, helyette még két feladat vár majd rá. Mindenekelőtt el kell hoznia Mükénébe Kerberoszt, az Alvilágot őrző háromfejű kutyát. Héraklész megkereste azt a barlangot, amelyen keresztül bejutott az Alvilágba. Annak gonosz lakói folyamatosan zaklatták és próbálták letéríteni őt útjáról. Rátalált Thészeuszra, akit büntetésből Kóré, az Alvilág királynője láncolt egy sziklához, mert ő segédkezett egyik társának abban, hogy elrabolják őt otthonából. Héraklész kiszabadítja barátját, aki korábban az amazonok elleni csatában  segítette őt.