After Herakles completed his first ten Labours, Eurystheus gave him two more claiming that neither the Hydra counted (because Iolaus helped Heracles) nor the Augean stables (either because he received payment for the job or because the rivers did the work). The first of these two additional Labours was to steal the apples from the Garden of the Hesperides.
Unsure where to go, Herakles first captured first captured Nereus (The Old Man of the Sea). Nereus was a shapeshifting god who was also known for his gift of prophecy and for never lying. Nereus, much like Proteus would only give answers to those who could defeat him. This is why when Nereus woke up and began changing shape into vicious creatures in order to get Herakles to let him go, Herakles held fast.
Nereus told Herakles where the Garden of the Hesperides and advised Herakles to get Atlas to pick the apples rather than do it himself.
Finally Nereus told Herakles that Atlas would make the offer to take the apples to Eurystheus himself if Herakles would just hold the sky a little longer. Nereus warned Herakles against that.
According to some versions Herakles was told by Nereus that in he would first have to slay the dragon Ladon who guards the apples because Atlas feared the dragon.
Herodotus claims that while on his way to Heracles stopped in Egypt, where King Busiris decided to make him the yearly sacrifice, but Herakles burst out of his chains.
Finally making his way to the Garden of the Hesperides, Heracles made a bargain with Atlas that if Atlas picked the apples Herakles would hold the sky for a while. Had Herakles not traded burdens this would have made this task (like the Hydra and Augean stables). When Atlas returned he decided that he did not want to take the heavens back, and attempted to trick Herakles by offered to deliver the apples himself if Herakles would just hold the sky a little longer (Atlas however had no intent on returning).
Remembering Nereus' advice not to accept the bargain Herakles pretended to accept the bargain, Herakles himself tricked Atlas. Herakles pretended to agree to the offer but asked that Atlas temporarily releave so that Heracles could take his lion skin pelt and make a padding of it so he could be a little more comfortable while Atlas went to take the Apples to Eurystheus. Atlas agreed, but as soon a he retook the heavens from Heracles, Herakles walked away, carrying the apples.
Either at the start of his elventh task or while returning to Tiryns after having acquired the apples Herakles encountered Antaios. Antaios a son of Poseidon and Gaia challenged everyone he met to wrestle him and had been believed invincible had made a shrine to Poseidon constructing it out of the bones of the men Antaios had killed wrestling. As Herakles was a formidable wrestler himself, he accepted the challenge.
Prior to the start of the match, while Herakles covered himself in oil as was the standard Antaios covered himself in dirt. Despite his strength Herakles could not ware Antaios down. Herakles realized that Antaios was invincible because as long as he touched the earth his strength was renewed by his mother Gaia (this being the reason Antaios had chosed dirt rather than oil before the match). With this revolation, Herakles took a new tactic. He lifted Antaios off the ground and shook off the dirt that Antaios had on him. After that he caught Antaios in a bear hug and lifted him off the ground and did not let him touch it. Being unable to renew his strength, Antaios was unable to match the might of Herakles who holding him aloft crushed his ribs and brought an end to Antaios.
Despite that the myth tells that Atlas picked the apples there is a detail of a Twelve Labours Roman mosaic (see below) from Llíria, Spain (3rd century) of Hercules stealing the golden apples from the Garden of the Hesperides