Город основали в IVвеке до н.э. купцы-мореходы из древнегреческого города Милеты и назвали его Феодосия, что в переводе с греческого означает «Богом данная». Однако, по заключению ученых, и до предприимчивых выходцев с Малой Азии (современной Турции) здесь уже было поселение местных жителей.
Довольно скоро Феодосия стала типичным небольшим греческим торговым центром, городом-государством. В 355 году до н.э. Феодосия была включена в состав Боспорского царства, которое через Феодосию экспортировало хлеб и другие товары в метрополию.
По свидетельству греческого историка Страбона, порт города мог принять до 100 судов, поэтому жизнь в порту кипела, и одно за другим отходили от его причалов груженые суда. Феодосия в те времена процветала, а роскошью и великолепием архитектуры могла соперничать с лучшими городами античного мира.
В первые века нашей эры на Феодосию совершались набеги захватчиков – сарматы, готы и, наконец, гунны, при нашествии которых в IV веке город был полностью разрушен и разграблен. Феодосия разделила участь всего Боспорского царства, а на протяжении последующих столетий существовала как небольшое селение.
В этот период в городе под названием Ардабра или Ардавда - «Город Семи Божеств (Светил)» жили аланы, входил он в состав Византийской империи, в VI веке был захвачен хазарами, но вскоре снова отошел к Византии.
