Glede časa nastanka mesta raziskovalci niso enotni. Mesto je bilo verjetno utrjeno naselje v 5. ali 6. stoletju na obrobju Bizantinskega cesarstva. Drugi pa so mnenja, da se je utrjena naselbina pojavila v 10. do 11. stoletju. V zgodnjem obdobju zgodovine mesta so ga naseljevali predvsem Alani, najmočnejše pozno sarmatsko pleme iranskega porekla. Na Krim so začeli prodirati od 2. stoletja našega štetja. Ko so se naselili na goratem Krimu, so Alani sprejeli krščanstvo. V pisnih virih se jamsko mesto omenja v 13. stoletju pod imenom Kyrk-Or ('Štirideset utrdb'). To ime je trajalo do sredine 17. stoletja. Leta 1299 je tatarska horda emira Nogaja napadla krimski polotok. Kyrk-Or so nato zasedali bizantinski vojaki. Trdna trdnjava se je uprla neposrednemu boju s Tatari, ki so si nato prizadevali oslabiti branilce z igranjem glasne glasbe tri dni in noči. Četrto jutro so bili branilci preveč izčrpani, da bi odvrnili nov napad in trdnjava je podlegla splošnemu pokolu. Ko so tako zasedli mesto, so Tatari v njem naselili garnizon. Na prehodu v 15. stoletje so Tatari pred vzhodno črto utrdb naselili karaitske obrtnike in postavili drugi obrambni zid, da bi zaščitili njihovo naselje in tako se je pojavil nov del mesta.

V 15. stoletju je prvi krimski kan, Hadži I. Geraj, ki je izkoristil prednosti trdnjave, stari del mesta spremenil v svojo utrjeno rezidenco. Krimski kanat je po porazu pri Zlati hordi postal bistveno močnejši. Pomen Kyrk-Ora kot trdnjave se je zmanjšal, krimski kan, Mengli I. Geraj, pa je svojo prestolnico preselil v Bahčisaraj. Staro mestno jedro je ostalo citadela Bahčisaraja in kraj zapora za plemiške ujetnike. Sredi 17. stoletja so Tatari zapustili Kyrk-Or. Tam so zaradi protijudovskih omejitev bivanja v drugih mestih Krimskega kanata živeli le Karaiti in več družin Krimčakov[1][2]. Tatari so Karaite smatrali za Jude, zato je mesto postopoma dobilo ime Čufut-Kale, kar v turščini pomeni 'judovska trdnjava' z negativnim in prezirljivim pomenom [3].

Po osvojitvi Krima in njeni vključitvi v Ruski imperij so prebivalci trdnjave smeli živeti kjer koli na Krimu. Od tega časa je bila Čufut-Kale zapuščen. Sredi 19. stoletja je mesto prenehalo obstajati.