Vienas iškiliausių Feodosijos viduramžių architektūros paminklų yra tvirtovė. XIII amžiaus 70-80-aisiais. tapo didelės Italijos prekybinės Genujos respublikos nuosavybe. Genujiečiai ją vadino Kafa. XIV amžiaus antroje pusėje. genujiečiai gerokai išplėtė savo valdas – užėmė Chembalo (Balaklava), o vėliau ir Surožą (Sudaką). Kafa tampa pagrindiniu administraciniu ir komerciniu Genujos valdų Kryme centru. Iš rytų čia buvo atgabenti prieskoniai, aromatinės medžiagos, šilkas, iš slavų kraštų atgabenti kailiai, vaškas, tačiau pagrindinė genujiečių prekė buvo „gyva prekė“ – vergai. Tai liudija daugybė dokumentų. Iki šių dienų išliko 36 notaro patvirtinti šio laikotarpio vergų pardavimo dokumentai. Dabartinės aikštės vietoje buvo Kafos vergų turgus (kan).
Sistemingi totorių antskrydžiai, liaudies sukilimai privertė genujiečius laikyti mieste didelius samdinių karinius būrius ir miesto sargybinius. 1307 m. Kafą užpuolė kipčakai ir totoriai, o tai atnešė miestui didelį sunaikinimą. Vėliau šis įvykis paskatino genujiečius statyti galingas gynybines struktūras. Miestą supo dvi tvirtovės sienų linijos, kurių storis iki pustrečio metro ir dvylikos metrų aukščio. Pastatyti 26 sargybos ir gynybiniai bokštai bei citadelė (tvirtovė tvirtovėje – kilus kariniams neramumams mieste). Iki šių dienų išliko didžiulių gynybinių konstrukcijų liekanos. O dabar miesto sode kyla trys Konstantino bokšto sienos. Bokštas buvo viduramžių Kafos gynybos vieta. Iš jo kilo tvirtovės sienos su penkeriais vartais, saugomais kareivių. Šalia bokšto galima pamatyti vėliau turkų pastatyto bastiono liekanas. Pietiniame Feodosijos pakraštyje, ant Karantino kalvos, buvo išsaugotos citadelės, kolonijos širdies, liekanos. Jį juosė siena su dvylika bokštų. Čia buvo visos svarbiausios genujiečių institucijos ir konsulinė pilis. Pačioje citadelėje gyveno tik genujiečiai.