В 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 веках становится могущественной и процветающей, широко известной в Европе и на Востоке как (важный Перевалочный пункт на Великом шелковом пути.