Наибольшую активность в освоении северо-причерноморских побережий проявил город Милет, находившийся на юго-западном побережье Малой Азии (эта область называлась Ионией) и заселенный греками-ионийцами (одна из групп эллинских племён). Он развивался весьма интенсивно, здесь быстрее, чем в других формирующихся полисах, созрели внутренние предпосылки для колонизации, кроме того, с середины 7-го века до нашей эры малоазийские греческие города страдали от агрессии восточных государств — Лидии, Мидии, а в 6 веке до нашей эры — Персии.
Первая половина — середина 6-го века до нашей эры — время наиболее активного оседания жителей Ионии за пределами своей родины. Греческий писатель Арриан называл Феодосию «древним эллинским городом, ионийским, колонием милетян». В Феодосии найдены фрагменты чернофигурной керамики и терракотовые статуэтки из Эллады, изготовленные не ранее второй половины 6-го века до нашей эры. Наиболее вероятное время основания Феодосии — около середины 6-го века до нашей эры.
Следующая волна колонистов приходится на рубеж 6-5 веков до нашей эры. Она связана с антиперсидским восстанием греческих городов Ионии, возглавленным Милетом и завершившимся поражением. Вполне вероятно, что тогда в Феодосию прибыла ещё одна партия переселенцев из Ионии.
В первой половине 4 в. до н. э. город вошел в состав Боспорской державы и получил новое имя — Феодосия — «Богом Данная». Имя города «Феодосия» мы впервые встречаем в источниках 4-го века до нашей эры — произведениях античных авторов, надписях Боспорского царства и на монетах, которые чеканил город. Очень важно замечание древнего грамматика Ульпиана: «Феодосия — местечко Боспора. Имя торжищу дано или от сестры, или от жены: об этом существует разногласие». Многие исследователи считают, что речь идёт о сестре или жене боспорского правителя Левкона 1, который, как мы увидим далее, завоевал независимое Феодосийское государство и присоединил его к своим владениям. Это печальное событие произошло в первых десятилетиях 4-го века до нашей эры. Отсюда следует, что раньше город имел другое имя. Какое?
Когда Феодосийское государство было независимым, оно выпускало монеты с надписями: «феодео» или «феодос». Это сокращённое слово, возможно, от мужского имени Теодеос, в состав которого входит слово «тео» (божество). Заметим, что на лицевой стороне ранних феодосийских монет отчётливо видна мужская голова. Известно, что греки нередко называли свои колонии именами их основателей (ойкистов), а после смерти чтили их как героев. Похоже на то, что и колонисты, осевшие на побережье Феодосийского залива, назвали свой город в честь его основателя, а в дальнейшем поместили его портрет (с лентой на голове, как признаком героизации) на своих первых монетах.
Когда Левкон 1 присоединил город к своему царству, он, по-видимому, переименовал его, назвав Теодосией (Феодосией), то есть Божьим даром. Нельзя не заметить, что новое название близко по звучанию к старому, не исключено, что таким способом боспорский царь старался вызвать расположение к себе своих новых подданных. Кроме того, Левкон чувствовал себя как бы вторым основателем города: в 4 веке до нашей эры, после присоединения к Боспору, Феодосия переживает период расцвета.
Для Левкона же и его преемников такое приобретение, как Феодосия, действительно стало «божьим даром»: за её счёт обогащались царское семейство и многие деловые люди на Боспоре. Весьма вероятно, что под божеством в новом названии города подразумевался Аполлон, который, во-первых, считался у греков покровителем колонистов, а во-вторых, являлся верховным божеством на Боспоре. Феодосийские монеты с изображением, возможно, Аполлона и надписью «феодос», отражавшей уже новое название города, могли быть отчеканены вскоре после его присоединения к Боспору. Легенды двух последующих монетных выпусков — «феудо» и «феу» — также представляют новое имя города — Феодосия.