Первой милетской колонией, появившейся в этих местах, стала Синопа (основана в 756 г. до Р.Х.). По истечению некоторого времени сами синопцы вывели к востоку от себя колонию Трапезунд, ставшую вскоре вторым по значению греческим городом на южном берегу Черного моря. Колонии милетян на западном и северном берегах появились значительно позже. Помимо дальности расстояния причина этой задержке крылась в характере местного населения. Ведь соседями греков здесь были не мирные пафлагонцы и фригийцы, а воинственные скифы.
Первой колонией милетян на западном побережье Черного моря стала Истрия, основанная в 657 г. до Р.Х. чуть южнее дельты Дуная (греки называли эту реку Истром). Вскоре по соседству возникли другие города милетян – Аполлония Понтийская (основана в 610 г. до Р.Х.), Одесс и Томы.
На северном берегу Черного моря милетяне появились только в конце VII в. до Р.Х. Их первой колонией здесь стало небольшое поселение на острове Березань, неподалеку от того места, где в Черное море впадали Южный Буг и Днепр. В первой половине VI в. до Р.Х. греки перебрались на материк и основали на правом берегу Буга город Ольвию. Место было очень удобно для жизни: по берегам тянулись прекрасные тучные пастбища, плодородная земля давала прекрасные урожаи, а в устьях обоих рек роились бесчисленные стаи рыб, в том числе огромные осетры, а также тунец и макрель. Не удивительно, что в середине VI в. до Р.Х. Ольвия начала стремительно расти. Причем граждане полиса (общее число их, как считают, могло достигать 10 тыс. человек) селились не только в городе, но также на берегах Бугского и Березаньского лиманов, где появилось несколько десятков небольших городков и сел. Их жители занимались земледелием и выращивали хлеб на продажу. Верховным органом власти было народное собрание граждан, ведавшее всеми важнейшими государственными делами. Дела для рассмотрения в народном собрании подготовлял специальный совет, состоявший из выборных членов и заседавший в храме Зевса. Исполнительная власть осуществлялась коллегиями выборных магистратов, важнейшей из которых была коллегия пяти архонтов во главе с первым архонтом. Архонты могли созывать народное собрание, они ведали внешними сношениями города, наблюдали за государственными финансами и выпуском монеты. Шесть стратегов управляли военными делами. Агораномы осуществляли полицейские функции, следили за порядком в городе, в частности на агоре, за торговлей на рынке, за правильностью мер и весов.
Видимо, в VI в. до Р.Х. милетцы на правом берегу Днестровского лимана основали Тиру, а на противоположном берегу лимана в том же веке возник город Никоний.
Одновременно милетяне осваивали берега Крыма, населенного в то время скифами и таврами. Первой греческой колонией в Крыму стал Пантикапей, основанный около 600 г. до Р.Х. Он возник на месте прежнего киммерийского поселения в области с очень плодородными землями. Кроме продажи хлеба большие доходы городу приносила посредническая торговля с местными племенами. Неподалеку от Пантикапея милетяне в середине VI в. до Р.Х. основали Феодосию. Город занимал плодородную равнину и обладал гаванью, которая могла вместить 100 кораблей. Третьим греческим поселением в этой области стал Нимфей.
Тогда же греки проявили интерес к Азовскому морю (они называли его Меотидой) – хоть и бурному, но чрезвычайно богатому рыбой. Основные их колонии располагались по берегам нынешнего Керченского пролива (греки именовали его Боспором Киммерийским). Главным городом здесь была Фанагория, основанная правда не милетянами, а выходцами из Теоса (в 540 г. до Р.Х.). Зато милетянам принадлежала самая дальняя из греческих колоний в черноморском бассейне – город Танаис, возникший между 625 и 600 гг. до Р.Х. в самом устье Дона. Это был общий торговый центр азиатских и европейских кочевников с одной стороны и прибывавших на кораблях греков – с другой.
Несколько колоний милетян появилось и на восточном, кавказском, берегу Черного моря. Здесь в VI в. до Р.Х. выросли два больших греческих города – Диоскуриада и Фасис. Об истории и даже точном местоположении первого мы фактически ничего не знаем. Фасис был основан в 520 г. до Р.Х. милетянином Фемистагором на плодородной равнине в устье реки Фасис (так греки называли Риони).