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.
All of the stories are set in and around the Mediterranean Sea. In his later years, besides kicking butt in his home land of Greece, he takes off to Africa and the legendary city of Troy (which many say was located in modern day Turkey).
Pretty much the only time we hear about Heracles wandering too far from the Mediterranean is when he goes to the Caucasus Mountains, which to the ancient Greeks was the edge of the known world. The fact that Heracles would journey so far from Greece shows off just what an awesome hero he really is.