В XIII веке на руинах Феодосии возникает новый город, получивший название Кафа. Генуэзские купцы выкупили у татарского хана Оран-Тимура развалины бывшего
мегаполиса и создали резиденцию Генуи в Крыму.
В XIV-XV веках опасаясь набегов татар, город был обнесен мощными стенами (до 12 метров высоты и 2,5 метров толщины) с 30-ю башнями окруженными рвом, наполненным водой.
Цитадель была возведена на крутых склонах вокруг Карантинного холма, и состояла из Консульского дворца, казначейства, резиденции латинского епископа, здания суда. Второй пояс стен окружал сам
город с лавками, мастерскими и домами простых горожан.
В 1308 году Кафу разгромили татары и это название города осталось в истории.
На территории цитадели до наших дней сохранилась южная стена цитадели с двумя башнями - Святого Климента (в четь римского папы Климента VI) и башня Криско. А также несколько
башен в разных частях города - Доковая, Константина, Джиованни ди Скаффа или круглая. Крайней южной точкой укреплений была башня Фомы у подножья холма Митридат.