I ricercatori non sono unanimi per quanto riguarda l'aspetto della città. La città era probabilmente un insediamento fortificato nel V o VI secolo sulla periferia dell'Impero bizantino. Altri ritengono che l'insediamento fortificato sia apparso nei secoli XI-XI. Durante il primo periodo della storia della città, venne abitata principalmente dagli Alani, la più potente delle tribù sarmate di origine iraniana. Iniziano a penetrare la Crimea dal II secolo d.C. Allontanandosi nella Crimea montuosa, gli Alani adottarono il Cristianesimo. Nelle fonti scritte la caverna è menzionata nel XIII secolo sotto il nome di Kyrk-Or (Quaranta Fortificazioni). Questo nome è durato fino alla metà del XVII secolo. Nel 1299 l'orda tatara di Emir Nogai conquistò la penisola di Crimea. Kyrk-Or era tra le città saccheggiate. Dopo aver devastato la città, i tatari distrussero la loro guarnigione. Alla fine del XV secolo, i tatari stabilirono degli artigiani caraiti davanti alla linea orientale delle fortificazioni e costruirono una seconda parete difensiva per proteggere il loro insediamento e quindi apparve una nuova parte della città.

Nel XV secolo il primo Khan di Crimea, Hadji-Girei, realizzando i servizi della fortezza, trasformò la vecchia sezione della città nella sua residenza fortificata. Dopo la sconfitta dell'orda d'oro, il Khanato di Crimea è diventato notevolmente più forte. Il significato di Kyrk-Or come roccaforte è diminuito e il Khan di Crimea, Menglis-Girei, ha trasferito la sua capitale a Bachčysaraj. Il centro storico rimase una cittadella di Bachčysaraj e un luogo di incarcerazione per i prigionieri aristocratici. A metà del XVII secolo i tatari hanno lasciato Kyrk-Or. Solo caraiti e diverse famiglie Krymchak[1] rimasero a vivere lì a causa delle restrizioni anti-ebraiche sui soggiorni in altre città del Khanato di Crimea.[2] I tatari consideravano i Caraiti come ebrei, perciò la città acquisì gradualmente il nome di Chufut-Kale, che in turco significava "fortezza ebraica" con un significato negativo e sprezzante.[3]

Dopo la conquista della Crimea e la sua inclusione nell'impero russo, gli abitanti della fortezza sono stati autorizzati a vivere ovunque in Crimea. Da quel momento in poi Chufut-Kale venne abbandonata. Alla metà del XIX secolo la città cessò di esistere.