В начале V века до н.э. экономическая, политическая и военная обстановка в северо–восточном Причерноморье привела к образованию Боспорской державы. Это государственное объединение со столицей в Пантикопее включило в свой состав греческие города по обеим берегам Боспора Киммерийского (Керченского пролива) и ряд местных варварских племен. По сообщению античного историка Диодора, в течение 42 лет Боспор управлялся Археанактидами. В 438-437 годах до н.э. власть в Боспорском государстве перешла к Спартоку. Возможно, он принадлежал к местной племенной знати, тесно связанной с греческими верхами общностью торговых и прочих интересов. Потомки Спартока – Спартокиды – правили Боспорским царством более 300 лет. С утверждением власти Спартокидов на Боспоре совпадает начало военной экспансии, направленной в сторону варварских племен на Таманском полуострове и на запад – к Феодосии.
К этому времени милетская апойкия на берегу Феодосийского залива превратилась в крупный экономический центр Причерноморья. Основой экономики полиса являлось земледелие и торговля. Греки быстро оценили достоинства удобной и безопасной феодосийской гавани, плодородие земель (по Страбону, в начале I в. н.э. урожай зерновых на землях к востоку от Феодосии составлял «сам – тридцать»), возможности торговли с проживавшими вблизи города варварами. В конце V века до н.э. город начал чеканить собственную монету, преимущественно, мелких номиналов. Экономическое благосостояние полиса сделало его конкурентом крупнейших городов Боспорской державы – Пантикапея и Фанагории. Возможно существовал и политический конфликт. Античные авторы сообщают о проживании в Феодосии изгнанников из Боспора. Большинство исследователей видит в этих изгнанниках сторонников свергнутых Археанактидов. В начале IV века до н.э. постепенно развивавшиеся между Боспором и Феодосией экономические и политические противоречия привели к открытому вооруженному конфликту.
Боспоро–Феодосийская война имела место в первой половине IV века до н.э. Согласно античным авторам Гарпократиону и Ульпиану, во время осады Феодосии (в 389-388 годах до н.э.) умер боспорский правитель Сатир. Войну продолжил его сын Левкон I. На стороне Феодосии выступила Гераклея Понтийская – древнегреческий город на южном берегу Понта Эвксинского, метрополия Херсонеса Таврического. С Феодосией ее связывали общие торговые интересы, боязнь усиления Боспорского государства. Боспоро–Феодосийско–Гераклейская борьба нашла яркое отражение в античной литературной традиции (Псевдо–Аристотель, Полиен и др.). Гераклеоты оказывали своим союзникам материальную и военную помощь: посылали продовольствие, направляли к осажденному городу флот, высаживали десанты на боспорской территории. Однако, несмотря на трудности, Левкону I удалось подчинить Феодосию. Первое упоминание о Феодосии в составе Боспорской державы содержится в речи знаменитого афинского оратора Демосфена «О беспошлинности», произнесенной в 355-354 годах до н.э. В ней говориться а «новом порте Феодосии, устроенном Левконом…» Длительный период название «Феодосия» входило в официальный титул Спартокидов, которые именовались «архонтами Боспора и Феодосии».
О времени появления названия «Феодосия» уже полтора столетия ведутся дискуссии. (Вопрос об изначальном названии нашего города в античную эпоху поставил русский историк Б. В. Кёне в середине XIX века. Он обратил внимание на различное написание демотикона /название полиса/ на феодосийских монетах: «ΘΕΟ», «ΔΕΟ(Ω)», «ΘΕΥΔΟ», «ΘΕΥ» Формы «ФЕОДО», «ФЕВДО» и «ФЕЙ» являются сокращением названия «Феодосия». Но форма надписи «ФЕОДЕО» по правилам древнегреческой грамматики не может быть образована от слова «Феодосия». К тому же упоминания г. Феодосии в античной литературе и эпиграфике появляются только в ΙV веке до н.э. Б. В. Кене сопоставил эти факты с замечанием позднеантичного грамматика Ульпиана (III в.) в его схолии к речи «О беспошлинности» Демосфена: «Феодосия /это/ Боспорское местечко. Имя торжища по сестре или по жене: /об этом/ разногласие…». Б. В. Кене высказал предположение, согласно которому в надписи «ΘΕΟΔΕΟ(Ω)» отразилось первоначальное негреческое название города «ФЕОДЕА» или «ФЕОДЕИА». После завоевания города Левконом I это древнейшее название было заменено им на близкое по звучанию Θεοδοσια).
В начале ХХ века гипотезу Б. В. Кене поддержал английский исследователь Э. Миннс. Дальнейшую разработку идея получила в 50–е годы ХХ века. В ходе археологических раскопок на Карантинной горке в 1949 и 1951 гг. были найдены обломки местной лепной керамики с прочерченным орнаментом, которые автор раскопок И. Б. Зеест датировала концом VII – началом VI веков до н.э. Д. Б . Щелов, ссылаясь на эти находки ( впрочем, необходимо отметить, что их датировка не является бесспорной) выдвинул версию о существовании варварского поселения, на месте которого и возник и название которого перенял древнегреческий полис.
Другой видный советский историк и археолог В. Д. Блаватский придерживался традиционной точки зрения. По его мнению изначальное название — Феодосия («Богом Данная») которое вполне уместно для города, возникшего на плодородной земле и обладавшего превосходной гаванью. Вместе с полным название очень рано в разговорном языке появилась сокращенная форма Феодея, отразившаяся в монетной легенде («ФЕОДЕО»). Таким образом Левкон I не изменял наименования полиса, а разногласия на которые ссылается Ульпиан, возникли в римское время, во II или III веках н.э. В 80–е годы известный крымский ученый – эпиграфист Э. И. Соломоник предположила, что город первоначально мог быть назван именем ойкиста (предводителя первого отряда колонистов), некого Феодеоса или Деоса. Случаи названия новых городов именами ойкистов были нередки в греческой колонизационной практике (например, древнегреческий город Гермонасса (современная станица Таманская) на северо-восточном берегу Черного моря).