Artifacts from the very western end of the Mediterranean and the coasts of Iberia beyond show up in Greek contexts during the 7th century, brought there presumably via Phoenician intermediaries. According to Herodotus, the earliest Greek to directly exploit the Tartessian trade was one Colaeus of Samos, a trader who usually covered the routes between Ionia and Egypt.
On one occasion, says the historian, this Colaeus was driven by a storm into the western Mediterranean, eventually making landfall in Tartessus, where he was well-treated by that region's long-ruling king Argantonius, who sent him back with riches beyond anything he had known before. This event is generally dated to somewhere around 638 BC, and the same author also recounts Phocaean expeditions reaching Argantonius' silver-rich kingdom.
It was during this time period, during which the Phoenician city states of the Lebanon, beset by the rapacious Assyrians and Babylonians, entered a terminal decline, and before the Tyrian colony of Carthage came to prominence in the Mediterranean, that Greeks could - and did - reach the Atlantic coasts, bringing back tales of such wealth and splendour that subsequent authors would hardly resist making use of this new geographical knowledge, spread about in knowing whispers, as apt settings for mythological events.
Herodotus also records that the Phocaeans too developed an interest in the area of Tartessus and the Pillars during this period. Duane W. Roller posits that Phocaeans indeed extended the reach of Greek geographical knowledge at around 600 BC, with expeditions beyond the Pillars, hugging the coastline of modern-day Portugal at least as far as Cape Roca near Lisbon, giving descriptive names to various landmarks attested in the late Roman source Avienus, namely Onoussa ("donkey-like") and Ophioussa ("snaky"), the latter of which Roller notes is "the more remote - and farther north" which "may indicate the limit of Phokaian penetration." Another place name of the same species is Cotinussa, the "island of Olives," which is associated with the largest of three islands in the Gades archipelago [Timaeus, BNJ 566 F 67, apud Pliny the Elder, NH 4.120].
The Phocaeans were also involved in colonisation in the western Mediterranean: their most famous colony was Massalia (moder Marseille, France), founded about 600 BC, with a subsequent foundation at Emporion (Empúries in Catalonia). The former would go on to hold its own as a seat of exploration, with two sons of the city - Euthymenes (see below) and Pytheas - making significant contributions to Greek knowledge of the regions outside the Pillars.
The next exploration to consider is that of Midacritus, an obscure figure, of whom Pliny the Elder [7.56.3] says curtly: -
Tin was first imported by Midacritus from the island of Cassiteris.
This brief allusion is the sole testimony of what must have been a highly important Greek expedition beyond the Pillars. Midacritus - whose name suggests that he was possibly of Phocaean origin - is a potential source for the Phocaean elements identified by Roller and others in Avienus. The precise location of Cassiteris - which would later take on a considerable sheen of mythology (leading Herodotus for one to reject it as fable) - remains unclear, with various theories placing it off Galicia, Britanny or even Cornwall. Almost certainly the rise of Carthage, replacing its Phoenician relations as the masters of the western seas, put paid to Greek interests in the area and led to their exclusion.
Travelling south along the African coast leads to a place known as the Emporicus Gulf. It is in this region that Strabo [17.3.3], on the authority of one Ophelas (whose work is dismissed as a fantasy), locates a particularly odd phenomenon, with associations with Heracles: -
Now they say that the Emporicus Gulf has a cave which at the full tides admits the sea inside it for a distance of even seven stadia, and that in front of this gulf there is a low, level place containing an altar of Heracles, which, they say, is never inundated by the tide - and it is this that I regard as one of their fabrications.
This wonder is also described by Pliny the Elder [5.1] and Maximus of Tyre : -
Euthymenes of Massalia, perhaps active towards the end of the 6th century, is remembered in a number of later testimonies for his claim to have crossed the Atlantic [FGrH V 2207 T 2ac], reaching a freshwater sea populated by crocodiles, hippos and the like, which he theorised was the source of the inundation of the Nile, when preturbed by the Etesian winds. Duane W. Roller suggests that the phenomena reportedly witnessed by Euthymenes occur in the region of the Senegal river estuary, concluding that Euthymenes possibly reached this area.
By this time, however, the Carthaginians were tightening their grip on the Atlantic seaways, with knowledge slowly filtering to the Greeks of the exploits of two brothers, Hanno and Himilco, who journeyed respectively south and north along the coasts outside the Pillars.
Of these, Himilco's account is the less attested (appearing mainly in Avienus' late Ora Maritima [114-128, 380-385, 410-413]), but seems to have stressed various negative features of the ocean (at least when told to Greeks and Romans): the sea was difficult to cross, was shallow, lacked winds, and was filled with monstrous animals and seaweed. Nevertheless, it is possibly from Himilco that tidings were first brought about the Tartessian contacts with the Oestrymnides (perhaps in Brittany), as well as conditions among the Hierni of the Holy Island (almost certainly Ireland, though Heligoland in the North Sea has its supporters) and their neighbours the Albiones of Britain.
Hanno, by contrast, is credited with a rather more detailed description of his voyage, which reputedly passed a considerable way down the African coast.
Colonies were planted at Karikon Teichon (perhaps associated with the Carian people of Anatolia), Gytta, Acra, Melitta (cf Hecataeus, BNJ 1 F 357) and Arambys, as well as the famous island entrepôt of Cerne, and friendly contacts established with the Lixitae, a Libyan tribe inhabiting the aforementioned region of Lixus. Their relation of their surroundings perhaps served as Herodotus' source for his beast-infested portion of Libya.
Further south, the river Chretes was traced upstream as far as a lake featuring three islands, each larger than Cerne, and the Western Horn and Southern Horn were discovered, with the expedition reaching as far as the foothills about "a very high mountain, called Chariot of the Gods, [...] which seemed to touch the stars" , eventually finding a savage race of hirsute humanoids the Lixitae referred to as Gorillae on an island in the midst of a lake on another island near the Southern Horn.
A third possible Carthaginian (if he is not to be identified with the Magonid Hanno) is one Magus, mentioned as appearing at the court of the Sicilian tyrant Gelo with tales of his circumnavigation of Libya. Another possibility is that this man was a Zoroastrian priest, in which case his travels may be associated with the expeditions chartered by the Persian ruler Darius I.
Coming to King Xerxes from there, he related in his narrative that, when he was farthest distant, he sailed by a country of little men, who wore palm-leaf clothing; these, whenever he and his men put in to land with their ship, left their towns and fled to the hills; he and his men did no harm when they landed, and took nothing from the people except cattle. As to his not sailing completely around Libya, the reason (he said) was that the ship could move no farther, but was stopped.
This is Herodotus' description of the journey undertaken by the Achaemenid navigator Sataspes at the behest of his king, Xerxes I, as a punishment for a rape committed by Sataspes [4.43]. Though Xerxes was unconvinced by Sataspes' explanation of his failure (resulting in his execution), the stopping of the ship finds corroboration from elsewhere in Greek literature. The "little men," meanwhile, were also encountered by a group of Nasamoneans (a Libyan tribe), who ventured overland into what would appear to be West Africa [2.32]: -
After journeying for many days [from east to west] over a wide extent of sand, they came [...] to a plain where they observed trees growing; approaching them, and seeing fruit on them, they proceeded to gather it. When they were thus engaged, there came upon them some dwarfish men, under the middle height, who seized them and carried them off. [...] They were led across extensive marshes, and finally came to a town, where all the men were of the height of their conductors, and black-complexioned. A great river flowed by the town, running from west to east, and containing crocodiles. [...] Etearchus [...] declared that the Nasamonians got safe back to their country, and that the men whose city they had reached were a nation of sorcerers.
This somewhat disconcerting group also feature in Pliny's Natural History, the author of which explicitly calls them "Pygmies" [6.30]. Pygmies were associated with the ends of the earth in Greek mythology from an early period, featuring in Homer as opponents of the cranes on the shores of the great river Oceanus [Iliad 3.1 ff.], and are also located in India, for example, by Ctesias. Their flight in Sataspes also features in descriptions of trade with the Carthaginians in Herodotus, and Hanno's and pseudo-Scylax's periploi.