The stories of Heracles take place way back in the day. And we mean waaaaaaaay, back in the day. By the time writers started scribbling their versions of Heracles' adventures, the stories of his exploits had already been around for many years.
Some call the era of Heracles and his fellow heroes the Heroic Age, the time when the heroes were all direct descendents of the gods and the world was crawling with monsters that needed slaying. It's important to think about the fact that even to the writers who originally recorded the legends of Heracles, he was a figure from the distant past.
Heracles pulls off most of his Twelve Labors in his homeland, Greece, but some of his adventures take him a great distance from home.
He heads to the Atlas Mountains in Northern Africa to find the Golden Apples of the Hesperides.
He sails across the Atlantic ocean to get the Geryon's cattle from the island of Erytheia. The ancient Greeks called the Atlantic simply Oceanus, and thought of it as giant river that encircled the world. Heracles showed just how awesome a hero he was by making it to a place that was so far away.
Heracles also takes a trip to the underworld (a.k.a. Hades), where he captures Cerberus, the hellhound. The land of the dead is probably the most dangerous and treacherous place he could possibly go. The underworld is on the list of places to visit for lots of other Greek heroes as well. Odysseus, Theseus, Orpheus were all said to have taken their own treacherous journeys there.