Der Bau erfolgte im 13. und 14. Jahrhundert. Im Jahr 1226 erwarben genuesische Händler die Ruinen von Theodosia vom tatarischen Khan Oran-Timur und errichteten an deren Stelle die Festung Kaffa, die zum Zentrum der genuesischen Besitzungen am Schwarzen Meer wurde. Schon bald entwickelte sich Kaffa zum größten Transithandelszentrum internationaler Handel und zu einem wichtigen Stützpunkt der genuesischen Kolonien im Schwarzmeerraum. Durch Kaffa wurden Weizen, orientalische Gewürze, Gold und Edelsteine nach Europa exportiert. Die Stadt war weitläufig und reich – im Hafen lagen Hunderte von Handelsschiffen, und manchmal reichten die Anlegestellen nicht aus, um alle ankommenden Schiffe aufzunehmen. Man hörte die vielsprachigen Gespräche dutzender Nationalitäten: Hier lebten Griechen und Italiener, Armenier und Juden, Ukrainer und Bulgaren, Karämer und Tataren. Kaffa war auch ein Zentrum des Sklavenhandels. Historische Dokumente belegen, dass Kaffa im 12. bis 15. Jahrhundert das wichtigste Zentrum des Sklavenhandels im Schwarze-Meer-Gebiet war; sein Sklavenmarkt war sowohl den Genuesen als auch später den Türken bekannt. Die Festung Kaffa, die nach der Festung Thessaloniki in Griechenland die zweitgrößte ihrer Art war, gehörte zu den stärksten Festungen Europas. Sie verfügte über zwei Befestigungsringe: die Zitadelle und die äußere Stadtmauer. Die Zitadelle wurde in den Jahren 1340 bis 1343 am steilen Hang zum Meer errichtet und weitere zehn Jahre lang ausgebaut. Sie bestand aus Kalkstein, der mit Kalklösung gemischt und die Fugen sorgfältig verfüllt wurden. Die Baustoffe für die Festung wurden in der Regel an den Stellen gewonnen, an denen Gesteine an den Hängen der umliegenden Berge an die Oberfläche traten, oder vom Meeresboden. Die Länge der Mauern der Zitadelle betrug 718 Meter, von denen heute noch 469 Meter erhalten sind. Die Mauern erreichten eine Höhe von 11 Metern und eine Breite von 2 Metern. Der Umfang der äußeren Festungsmauer betrug fast 5,5 Kilometer und umfasste mehr als 30 Türme. Unter den Festungsmauern verlief ein tiefer Graben, der mit Wasser gefüllt war und sowohl als Verteidigungsanlage als auch als Kanal zur Ableitung von Regenwasser ins Meer diente. In seiner Form erinnerte die Stadtfestung an einen Amphitheater, dessen Bühne die Bucht von Theodosia bildete. Innerhalb der Zitadelle befanden sich das Konsulatspalast, das Finanzamt, die Residenz des lateinischen Bischofs, ein Gerichtsgebäude mit einem Balkon für die Verkündung konsularischer Entscheidungen, Kontore zur Überprüfung von Gewichten sowie Lager und Geschäfte für besonders wertvolle Waren wie Edelsteine, Felle und Seide. Im 19. Jahrhundert wurden die meisten Gebäude abgerissen. Bis heute sind nur noch der südliche Teil der Zitadellenmauer mit zwei Türmen (der Turm des Heiligen Klimens und der Turm Chrisco), ein Teil der westlichen Mauer, die Torspione sowie einige Türme in verschiedenen Teilen der Stadt erhalten geblieben. Auf dem Gelände der Zitadelle befinden sich außerdem eine Brücke, türkische Bäder und mehrere Kirchen.
