As Heracles was performing the tenth of the twelve labors, he came to the western edge of Africa, near to the coast of Europe (the modern-day Straight of Gibraltar). To celebrate his journey to where the ocean meets the land, Heracles erected two pillars.
When ancient authors mention the Pillars of Heracles, it is this place to which they are referring.
Source(s):
Apollodorus. Bibliotece.