A Herkules-barlangok a Spartel-fok közelében népszerű látványosságnak számítanak Marokkó északi részén. A barlangrendszernek két bejárata van, egyik a tengerre, másik pedig a szárazföldre nyílik. A tengerre néző járatot Afrika térképének nevezik, mert alakjában nagyon  hasonlít az afrikai földrészre. Dagály idején az Atlanti-óceán vize itt jut be a barlang alacsonyabban fekvő részeibe. Azzal kapcsolatosan, hogy Afrika térképe valóban természetes eredetű képződmény vagy sem, heves viták folynak. Többen is amellett voksolnak, hogy hajdanán a föníciaiak vájták ki furcsa formáját, akik Hanno vezetésével az egész afrikai kontinenst körbehajózták és ismerték annak partvonalait. Sőt akár földalatti járatokat is építhettek a Gibraltári-szoros alatt.

 A régészeti leletekből kiderült, hogy a Herkules-barlangokban már a neolitikum idején is laktak emberek i. e. hatezer körül. A mítoszok szerint egykor a föníciaiak ásták ki az alagutak mesterséges járatait, amit a barlang falain látható szem formájú rajzok is megerősítenek. Később a Marokkót elfoglaló berberek néhány sziklát elmozdítottak a helyükről, hogy malomköveket készítsenek belőlük. A külső járatok ennek az emberi beavatkozásnak az eredményei. A turizmus igényeinek megfelelően ezeket a részeket különböző, nagyrészt mitológiai elemeket felvonultató  szobrokkal és díszítményekkel tették látványosabbá. Először görög stílusú oszlopsorok fogadják a látogatókat, majd egy lejtőn lefelé haladva feltárul a barlang bejárata Héraklész szobrával. A nagy gonddal megtervezett látogatóközpont kialakításához az is hozzájárult, hogy nem messze innen épült fel a marokkói király nyári palotája, valamint  akörnyék védett területté nyilvánítása. 

A barlangokról sokáig azt hitték, hogy feneketlenek, mivel nem tudni hol érnek véget és merre ágaznak szét a különböző járatok. Sokan azt hangoztatják, hogy egy több mint huszonnégy kilométer hosszú földalatti alagútnak a végei, amely a Herkules oszlopai (Gibraltári-szoros körli hegyek) alatt folytatódik a tenger alatt és az Ibériai-félszigeten ér véget Gibraltáron, a Szent Mihály-barlangnál. A berber makákók kapcsán is felbukkan ennek a tenger alatti alagútnak a legendája. Ezek a majmok az Afrikát Európától elválasztó szoros mindkét felén azért honosodhattak meg, mert régen a berberek Marokkóból a föld alatti járatokon keresztül betelepítették őket Európába. Egyelőre nincs bizonyíték mindezek alátámasztására, de figyelembe kell vennük azt a tényt is, hogy a Herkules-barlang még rengeteg titkot rejt magában, hiszen nagy része még feltáratlan.

 A görög legendákban Héraklész ebben a barlangban pihent meg, mielőtt elvégezte volna utolsó próbatételét, a Heszperidák aranyalmáinak megszerzését. A sötét járatokban Gerüón óriás rejtőzött, aki az egyik halhatatlan gorgó véréből született. Gerüón három feje  a derekánál összenőtt, majd mind a hat lábánál ismét szétvált. Bíborszínű tehenekből álló csordáját az Orthos nevű kétfejű kutya őrizte. Héraklész végül elhajtotta Gérüón csordáját, majd végzett az óriással és a kutyájával. Az értékes gyümölcsöket rejtő kertet azonban nem volt könnyű megtalálni, mert nagyon jól elrejtették a magas Atlasz-hegység sziklái. Ahelyett, hogy megmászta volna a hegyeket, Héraklész emberfeletti erejével áttört rajtuk. Így összekapcsolta az Atlanti-óceánt a Földközi-tengerrel, és létrehozta a Gibraltári-szorost. A kettéhasadt hegy egyik része Gibraltár sziklája (brit fennhatóság alatt) és a Ceuta városa fölött magasodó Hacho-hegy Spanyolországban, míg  a másik fele a marokkói Musa-hegy, amely Mons Abyla néven is ismert. Ezt a két hegyfokot a Gibraltári-szoros mentén  azóta is Herkules oszlopaiként ismerik. Diodorus Siculus feljegyzéseiben azonban egy másik legenda is felbukkan a szoros eredetével kapcsolatosan. Szerinte Héraklész csak leszűkítette a már meglévő szorost, hogy megakadályozza az Atlanti-óceánból érkező szörnyek bejutását a Földközi-tengerbe.

Amikor Héraklész megérkezett végső céljához hosszú útjának legvégén, Atlasz titánnal találkozott. Őt éppen Zeusz, a hős apja és egyben az istenek királya ítélte arra a sorsra, hogy tartsa örök időkön át az eget karjaival. A titán nem igazán élvezte keserves feladatát, ezért mindenáron meg akart szabadulni terhétől. Héraklészt azzal ámította, hogy abban az esetben, ha megtartja helyette az eget, ő elmegy a Heszperidák kertjébe és hoz neki az aranyalmákból. Héraklész úgy tett, mintha beleegyezne az ajánlatba, ezért át is vette Atlasz terhét. Miután a titán visszatért az almákkal, rögtön közölte Zeusz fiával, hogy becsapta őt.  Abba viszont belement, hogy feladja a hősre a földön fekvő köpenyét, hogy annak segítségével ne valljon kudarcot és meg tudjon birkózni feladatával. Egy rövid pillanatig, miközben a ruhát ráadta, az ég ismét az ő vállára nehezedett. Héraklész ezután fogta az almákat és gyorsan elrohant a helyszínről. Egy másik verzióban azonban Atlasz nem Héraklész ellenfele, hanem jövendőbeli apósa lesz. Ebben az arab történetben Atlasz három lányát az aranyalmákat termő kertben rejtette el, hogy megóvja őket mindenféle veszedelemtől. Ladónt, a sárkányt bízta meg azzal a feladattal, hogy minden arra tévedő embert pusztítson el. Ez így is ment egész addig, amíg Héraklész meg nem érkezett a helyszínre. A sárkánnyal történő dulakodás közben a közeli hegy kettévált, és a Földközi-tenger kék vize összekeveredett az Atlanti-óceán zöldjével, Európa pedig elvált Afrikától. Héraklész  a csatát követően feleségül vette az egyik lányt, akinek Tangis volt a neve.  Róla nevezték el később a barlanghoz legközelebb fekvő nagyvárost, Tangert.