В 80-х годах IV в. до н. э. Феодосия была завоевана соседним Боспорским царством, столицей которого был Пантикапей (Керчь) и становится центром хлебного экспорта.

 

Значение крупного торгового центра Боспора Феодосия сохранила до IV века нашей эры. В конце III и начале IV веков на территории Крыма проживают кочевые племена - аланы, сарматы, готы. Около 370 г. н. э. с Таманского побережья на Керченский полуостров прорвались орды гуннов. Они предали огню и мечу многие города и селения Боспора. Была разрушена и Феодосия. Под ударами гуннов распалось тысячелетнее Боспорское государство. Так закончился античный период Феодосии. В 679 году временное затишье на полуострове было нарушено новыми пришельцами - хазарами. Правитель нового монархического государства Хазарии именовался каганом (князем). 
В начале XI века в Хазарию вторглись сначала печенеги, затем половцы, господствовавшие на полуострове около 200 лет. В 1223 г. половецкому господству положили конец татаро - монголы, которые окончательно утвердились на полуострове в 1239 году. Наследники золотоордынского хана Батыя, который умер в 1255 г., Мангу - Тимур, а затем Оран-Тимур в 1266 году получили во владение города Керим (Старый Крым) и Кафу.
Генуэзцы по договоренности с Оран - Тимуром приобрели прибрежную полосу земли за значительную сумму (и обязались платить пошлину за ввоз и вывоз из города товаров), построили порт и крепость недалеко от того места, где была древняя Феодосия. Город назвали «Каффа» (в латинской транскрипции часто встречается «Gaffa» с двумя буквами f, у некоторых исследователей - «Кафа»). 
Впервые имя Кафа встречается у византийского писателя X века Константина Багрянородного (913-959 гг.) в повествованиях о происшествиях IV века н. э. (Петр Кеппен. О древностях Южного берега Крыма и гор Таврических. 1837.). Византийский историк Никифор Григорас пишет: «Генуэзцы недавно основали город Каффу (он пишет около XIV века), по условию и с дозволения скифского владельца (на самом деле татарского Оран-Тимура), но город сей не был сначала, ни так велик, ни так хорошо укреплен стенами, как теперь. Генуэзцы сперва довольствовались небольшим пространством земли, на котором жили без всякой ограды, как только рва и насыпного вала. После сего стали тайно провозить сухим путем и морем камни и другие материалы для строения и распространили селение свое в ширину и вдоль берега, подняли дома свои выше и, наконец, заняли места больше, нежели им отведено было». К 1318 году Каффа превратилась в крупнейший многонациональный средневековый город. Папа римский Иоанн XII, видя цветущее состояние города, учредил в нем епархию. В этом же году генуэзцы окружили город оградой из бревен, скрепив их цементом, а в 1352 г. при консуле Готтифредо де Зоалио начали заменять эту ограду каменной стеной с высокими башнями и несколькими крепко запираемыми воротами.
Через некоторое время Каффу уже надежно защищали две линии мощных крепостных сооружений.
                     
Первая линия в окружности 718 метров и 12 крепостными башнями (1340-1352 гг.), вторая, внешняя линия оборонительных сооружений, длиной в 5,5 км с 26 башнями (есть данные о 30 башнях) сооружалась в 1382-1385 гг. при консулах Бартоломео де Якопо (1382 г.), Мельядуче-Каттанео (1383 г.), Джиакомо Спинола (1384 г.), Пьетро Газано и Бенедетто Гримальди (1385-1386 гг.). Все консулы, а их по списку, составленному профессором Юргевичем, с XIII в. по 1475 г. было 82, в какой-то мере стремились укреплять стены крепости, украшая ее величественными башнями. До наших дней сохранились названия только некоторых из них: св. Константина, св. Климента, св. Антония, Доковая, башня Криско, св. Федора (1384 г.), св. Фомы.История города, который был разбит на многочисленные кварталы согласно национальным, конфессиональным признакам и профессиональной принадлежности. В районе Карантина армяне имели целый квартал, своего рода крепость Айоц Берд, окруженную каменной стеной. Из 70 тысяч населения Каффы (в других источниках 80 тысяч) 30 тысяч составляли армяне. Они имели в Каффе своего епископа. В Уставе Каффы 1316 года упоминаются три древних армянских церкви в городе, а в окрестностях - монастыри. Благодаря острой конкуренции Генуи и Непеции Кафа в XIII-XV веках становится могущественной и процветающей, широко известной в Европе и на Востоке как (важный Перевалочный пункт на Великом шелковом пути.

В Каффе этими торговыми сделками занималась коллегия св. Антония. За каждого купленного или проданного раба чиновники этого ведомства получали специальное вознаграждение.
Тысячи несчастных пленников - русских, украинцев, лезгин, черкесов, абхазцев - продавались на невольничьих рынках в Каффе по очень высокой цене. Их увозили в переполненных трюмах на морских судах в Италию, Египет, Сирию, Турцию. Каффу посещали не только купцы и мореплаватели из разных стран, но и путешественники, ученые, государственные деятели, дипломаты. О ней писали многие византийские историки, летописцы, известные арабские географы. 
В своих произведениях, отчетах и мемуарах они называли Крым островом Каффа, а саму Каффу - жемчужиной морей;.
Путешественники, историки писали, что с начала XV века в Каффе было 6000 зданий в центральной части города, столько же в предместьях, а в более отдаленных районах свыше 11 тысяч. Это означает, что население города Каффы вместе с окраинами действительно составляло не менее 80 тысяч человек. И это был один из самых многолюдных городов не только на побережье Черного, но и Средиземного морей. 
Как же выглядела в те времена цветущая и благоденствующая Каффа 
Поблизости дворца находилось казначейство и монетный двор. На каффинском монетном дворе чеканились монеты медные (фолери) и серебряные (аспры). Монеты были, как правило, двуязычные, выпускались с надписями и атрибутами на латинском и арабском языках. Например, на аспрах было изображение генуэзского герба (портал и ворота), начальная буква фамилии консула с латинскими буквами CAFA по кругу, а на оборотной стороне татарская тамга крымского хана, на арабском языке надпись и несколько звездочек. Редко встречаются медные фолери с изображением Георгия Победоносца, поражающего копьем змея. Каффинские аспры и фолери имели хождение во всех генуэзских факториях. 
Рядом с дворцом стояло здание курии, где консул три раза в неделю творил суд и расправу, по соседству располагалась городская ратуша с широкими мраморными лестницами, украшенными статуями рыцарей в полном вооружении. 
С лоджии ратуши глашатай торжественно в сопровождении трубача созывал ежемесячно народ и зачитывал постановления консула или приговоры суда. Консул возглавлял высший правительственный совет, куда входили два заседателя, секретарь, четыре судьи и комендант. 
Город был застроен красивыми домами, дворцами консулов и вельмож, великолепными храмами с многочисленными журчащими фонта нами. В центре цитадели возвышался великолепный консульский замок - дворец, украшенный мечами, рыцарскими доспехами, геральдическими щитами, скульптурными украшениями и мраморными барельефами копиями портретов античных героев, многочисленными гербами консулов, дожей, императоров. На цоколе консульского дворца гордо развевался флаг генуэзской республики: серебряный крест от края и до края щита на червонном поле. Внутри дворец также был украшен мраморными бюстами, скульптурами, восточными коврами, дорогим оружием, рыцарскими доспехами, венецианскими зеркалами, картинами художников средневековья.
В залах дворца, на стенах, обшитых панелями из можжевелового и кривого дерева, висели дамасские мечи, красовались чучела из добытых на охоте в окрестных лесах оленей, косуль, вепрей и волков. К потолку были подвешены хрустальные люстры, которые вспыхивали огнями свечей во время торжественных приемов и праздников. Консулу принадлежало «право меча», и в большом приемном зале дворца на видном месте выставлялись символы неограниченной власти - меч и скипетр. 
В 1472 году при консуле Эрасто Джустиниани Каффинский монетный двор прекращает чеканку своей монеты.Каффинский порт - гавань производил большое впечатление на всех прибывающих с различными миссиями иностранцев. Путешественники, описывая его размеры, приводят внушительные цифры (от 200 и выше) размещавшихся в нем торговых и иных судов. Сюда привозили восточные ткани, китайские шелка, восточные пряности и камни самоцветы ломбардское полотно, английское сукно, греческие вина. Русские купцы везли в Кафу знаменитые на весь мир дорогие меха из соболей и куниц, мед и льняные ткани. Но уже с середины XV века генуэзские колонии стали стремительно слабеть. Это было вызвано теми ограничениями, которые ввела Турция по следованию судов через проливы Босфор и Дарданеллы. Однако на этом ограничении султан Мехмед II не остановился. В его входило полное, безраздельное господство над всем бассейном черного моря.

К началу XVI века турки сосредоточили в Кефе большой арсенал, только одних артиллерийских орудий было около 800 штук.

Сам город не изменил свой архитектурный облик, новая застройка была такой же, как и в генуэзской Каффе. Большинство церквей генуэзской Кафы турки превратили в мечети. Челеби говорит, что в Кефе 60 алтарей - «михрабов единого бога» (то есть 60 мечетей) и 40 минаретов, девять мусульманских монастырей. XVII знаменует собой поворот в исторической судьбе Крыма. Русский и украинский народы принимали решительные меры к пресечению турецких набегов на свои земли. Были предприняты меры по укреплению южных границ и военные походы в Крым еще при Иване III. (1556 - 1559 гг.). Большую роль в этих походах сыграли запорожские казаки. В 1616 году запорожцы под командованием гетмана Конашевича - Сагайдачного взяли Синоп и Трапезунд, а при возвращении на челноках-чайках совершили дерзкий налет на Кефе, сожгли и потопили там турецкий флот, освободили тысячи пленников. В 1628 г. четырехтысячный отряд запорожских казаков во главе: гетманом Михаилом Дорошенко полтора месяца держали город Кефе в осаде, а в 1675 году героический поход в Крым совершил 20-тысячный отряд под командованием Ивана Сирко. Взяв главную турецкую крепость Кефе, запорожцы освободили около 7000 невольников. 

Вторая половина XVIII века ознаменовалась выходом России на берег: Черного моря. В 1771 году войска под командованием князя Долгорукого приступом овладели Кефе, а в 1774 году по Кучук-Кайнарджипскому договору Крым был уступлен России. В 1783 году Крым был включен в состав Российского государства, а в 1787 году Кефе был возвращено древнее имя - Феодосия.