The Black Sea region had passed a long way of historical development even before the emergence of Greek cities. There are evidences of ancient mythology, ancient historians, toponymy and archaeological sources of these remote times, though they are still unclear in many respects. In this historical period, on the northern shores of the Black Sea, the colonists-Greeks settlements arise, in whose face the local population enters into permanent intercourse with representatives of the ancient slave society for the first time. The centuries-old history of the Greek cities of the Black Sea region, their long relationship with the Scythians and other inhabitants of the region, the complex interrelationship of two cultures different both in origin and in inner content had led to the new historical and cultural situation in our South, in the conditions of which later the East Slavic tribes and the first Russian state had been forming. The first acquaintance of the brave Aegean navigators with inhospitable shores of Pontus was reflected in the myth of the Argonautic expedition. Then the myths of Iphigenia in Taurida, Achille on the island of Levka, the stay of Odysseus in the gloomy land of the Cimmerians followed. The final link is the fantastic geography of the Logographers with legends of the Hyperboreans and the struggle of the Arimaspians with vultures. Let us try to reveal the historical reality veiled by the fantasy of myth. Let`s establish the connection between the North Black Sea Region and the ancient states of the Mediterranean with the help of concrete historical evidence.