Освоение Черного моря через Проливы и Пропонтиду (Мраморное море) начинается, вероятно, с конца VIII века. Однако первые поселения были разрушены кимерийцами, и греки закрепились здесь на полвека позже. В VIII веке жители Милета основали Кизик на южном берегу Пропонтиды. В 676 году он был восстановлен после набега киммерийцев. Другие милетские поселения появились чуть позже, в частности Абидос на азиатском берегу Геллеспонта (Дарданеллы). Между Абидосом и Кизиком фокийцы основали Лампасак. Европейский берег позднее принял эолийцев с Лесбоса в Сеете, в Геллеспонте, а позднее, около 600 года, — ионийцев с Самоса в Перинфе. Все-таки один город материковой Греции — Мегара — составил конкуренцию греческим городам Азии: с 676 года он отправил колонистов в Калхедон, на восточный берег Босфора, а через шестнадцать лет, в 660 году, на противоположном берегу они основали Византий, снискавший впоследствии великую славу. То, что мегарийцы потратили семь лет, чтобы обосноваться на территории Византия, вызывало, по свидетельству Геродота, огромное удивление и презрение персидского военачальника времен Дария. Тем не менее мегарийские колонии Босфора теперь могли контролировать выход к Черному морю.
Греки называли его Понтом Эвксинским, или гостеприимным морем — в обратном смысле, поскольку страшные бури, туманы и ветра, обрушавшиеся на это море без островов, усложняли судоходство. Они исследовали его берега, начиная с Босфора, одновременно в двух направлениях: на восток, в сторону Кавказа и мифической страны Золотого Руна — Колхиды, и на север, за устье Дуная, до Крыма. Милет играл здесь ведущую роль, второй была Мегара, как и в Пропонтиде. К 630 году переселенцы из Милета окончательно закрепились в Синопе, в центральной части северного берега Анатолии. Позже, в VI веке, за Синопой они основали Амис. Синопа же, в свою очередь, отправила колонистов дальше на восток, в Трапезунд. Эти города обязаны успехом не только животноводству, рыболовству и земледелию: морская торговля позволяла им зарабатывать на новых каналах сбыта, так как некоторые товары перевозились сухопутным транспортом по высоким анатолийским плоскогорьям из Синопы или Амисма через Киликию на Кипр.
Идя вдоль западного берега Понта Эвксинского, милетяне быстро достигли Дуная: немного южнее реки в середине VII века была основана Истрия. Десятью годами позже они закрепляются в Ольвии, в устье рек Буг и Днепр, который они называли Борисфеном. До конца VII века они осваиваились в Аполлонии на фракийском берегу, затем севернее, в Одессосе (Варне). В первой половине VI века они достигают Крыма (или Херсонеса Таврического), основывают там Пантикапей (Керчь) и Феодосию, а затем уходят в Азов, чтобы построить там город Танаис в устье реки Дон. На Каваказе также были созданы более мелкие фактории, например Фасис или Диоскурия. Мегарийцы, менее активные в этом плане, около 560 года основали Гераклею Понтийскую между Босфором и Синопой. В 510 году — Месембрию, между Аполлонией и Одессосом. И лишь в 422 году жители Гераклеи Понтийской закрепляются в Херсонесе, на южной оконечности Крыма.