Jednym z najwybitniejszych zabytków architektury średniowiecznej architektury Teodozji jest twierdza. W latach 70-80 XIII wieku. stał się własnością dużej włoskiej republiki handlowej Genui. Genueńczycy nazywali ją Kafa. W drugiej połowie XIV wieku. Genueńczycy znacznie rozszerzyli swoje posiadłości, zdobywając Chembalo (Balaklava), a później Surozh (Sudak). Kafa staje się głównym centrum administracyjnym i handlowym posiadłości genueńskich na Krymie. Przyprawy, substancje zapachowe, jedwab sprowadzano tu ze wschodu, futra, woski sprowadzano z ziem słowiańskich, ale głównym towarem Genueńczyków był „towar żywy” – niewolnicy. Świadczą o tym liczne dokumenty. Do dziś zachowało się 36 notarialnych dokumentów z tego okresu dotyczących sprzedaży niewolników. Targ niewolników Kafa (kan) znajdował się na miejscu obecnego placu.
Systematyczne najazdy Tatarów, powstania ludowe zmusiły Genueńczyków do utrzymywania w mieście dużych zaciężnych oddziałów wojskowych i straży miejskiej. W 1307 roku Kafa została zaatakowana przez Kipczaków i Tatarów, co przyniosło miastu znaczne zniszczenia. Później to wydarzenie skłoniło Genueńczyków do budowy potężnych struktur obronnych. Miasto było otoczone dwiema liniami murów obronnych o grubości do dwóch i pół metra i wysokości dwunastu metrów. Wybudowano 26 wież strażniczych i obronnych oraz cytadelę (twierdza w twierdzy - na wypadek niepokojów zbrojnych w mieście). Do dziś przetrwały pozostałości potężnych budowli obronnych. A teraz w miejskim ogrodzie wznoszą się trzy ściany wieży Konstantyna. Wieża była miejscem obrony średniowiecznej Kafy. Stąd pochodziły mury twierdzy z pięcioma bramami strzeżonymi przez żołnierzy. Obok wieży można zobaczyć pozostałości bastionu zbudowanego później przez Turków. Na południowych obrzeżach Teodozji, na Wzgórzu Kwarantanny, zachowały się pozostałości cytadeli, serca kolonii. Otoczony był murem z dwunastoma basztami. Tutaj znajdowały się wszystkie najważniejsze instytucje Genueńczyków oraz zamek konsularny. W samej cytadeli mieszkali tylko Genueńczycy.