There are countless myths relating to the superhuman efforts made to explore the territory lying beyond the northeastern Aegean. One of the earliest is the tale of Phrixos and Helle, a story marked by the tragic death of the heroine. It would, however, be many centuries and many more heroic deeds and sacrifices later before ships sailing from Aeolis, Ionia and Attica would bring the first Greek settlers to the Hellespont and the Propontis, and from there to the Euxine Pontus. The first long voyages and the adventures of the pioneering, daring seamen are all creatively mentioned in the legend of the Argonautic Expedition. The original account refers to a voyage which must have taken place during the fourteenth or thirteenth century BC, when the Mycenaean kingdoms flourished.

All myths connected with the Black Sea, the heroic deeds, the monsters, hybrid creatures like the Amazons and the woman-snake, the head-hunters who used to sacrifice shipwrecked sailors, as well as the sorceresses Medea and Circe, all the fantastic tales succesfully coexisted within the ancient Greek mentality.

The Black Sea might symbolically, be called Axenos Pontus (a propitiatory appelation of this Inhospitable Sea). Ancient authors of Late Antiquity mention Axenos Pontus, in their desire to stress the overwhelming difficulties and trials awaiting early seafarers, especially before the first Greek colonies were established along its coastline.