Viens no izcilākajiem Feodosijas viduslaiku arhitektūras pieminekļiem ir cietoksnis. XIII gadsimta 70-80. kļuva par lielās Itālijas tirdzniecības republikas Dženovas valdījumu. Dženovieši viņu sauca par Kafu. XIV gadsimta otrajā pusē. Dženovieši ievērojami paplašināja savus īpašumus, ieņemot Čembalo (Balaklava), vēlāk arī Surožu (Sudaku). Kafa kļūst par galveno Dženovas īpašumu administratīvo un komerciālo centru Krimā. No austrumiem šurp tika vestas garšvielas, aromātiskās vielas, zīds, no slāvu zemēm piegādātas kažokādas, vasks, bet dženoviešu galvenā prece bija "dzīvā prece" – vergi. Par to liecina daudzi dokumenti. Līdz mūsdienām ir saglabājušies 36 šī perioda notariāli apliecināti dokumenti par vergu pārdošanu. Kafa vergu tirgus (kan) atradās pašreizējā laukuma vietā.
Sistemātiskie tatāru reidi, tautas sacelšanās piespieda dženoviešus paturēt pilsētā lielas algotņu militārās vienības un pilsētas sargus. 1307. gadā Kafai uzbruka kipčaki un tatāri, kas pilsētai atnesa ievērojamus postījumus. Vēlāk šis notikums pamudināja dženoviešus būvēt spēcīgas aizsardzības struktūras. Pilsētu ieskauj divas cietokšņa mūru līnijas, kuru biezums sasniedza divarpus metrus un bija divpadsmit metrus augsts. Tika uzbūvēti 26 sardzes un aizsardzības torņi un citadele (cietoksnis cietoksnī - militāru nemieru gadījumā pilsētā). Līdz mūsdienām ir saglabājušās milzīgu aizsardzības struktūru paliekas. Un tagad pilsētas dārzā paceļas trīs Konstantīna torņa sienas. Tornis bija viduslaiku Kafas aizsardzības vieta. No tā nāca cietokšņa sienas ar pieciem vārtiem, ko apsargāja karavīri. Blakus tornim redzamas turku vēlāk celtā bastiona paliekas. Feodosijas dienvidu nomalē, Karantīnas kalnā, ir saglabājušās kolonijas sirds - citadeles - paliekas. To ieskauj mūris ar divpadsmit torņiem. Šeit atradās visas svarīgākās Dženovas iestādes un konsulārā pils. Pašā citadelē dzīvoja tikai dženovieši.