La ville a une longue histoire. Elle existait déjà dans la première moitié duXIIIe siècle, lorsque la Crimée fut conquise par lesMongols deBatou Khan sur laprincipauté de Théodoros. Les Mongols fortifièrent la ville, qui est devenue depuis lors une capitale de la « Yourte de Crimée » (province de Crimée de laHorde d'or) et le lieu de résidence de l'émir de Crimée. Au cours de cette période, la ville avait deux noms : les habitants turcophones et musulmans la nommaientQırım (du tatar de Crimée :qırım,« colline ») ; les chrétiensgrecs locaux l'appelaient engrec Κιμμέριος (Cimmérios comme le proche « détroitCimmérien ») ; enarménientcherkessogaïSourhkat, et enitaliengénoisSolcati (« sillon »,« fossé »).Solkhat est la forme turque du nom arméno-génois. La ville abrite toujours un monastère arménien, celui deSainte-Croix. Le nom turc de la ville,Qırım, a par la suite été donné àtoute la péninsule.
Depuis l'annexion de la Crimée parCatherine II de Russie, en1783, la ville est connue sous le nom russe de Staryï Krym, traduction russe du nom donné par les Tatars de Crimée, Eski Qırım.
Le célèbreécrivain russeAlexandre Grine (1880-1932) vécut et mourut à Staryï Krym : un musée lui est consacré dans la ville.
Staryï Krym abrite un important sanatorium pour cardiaques, qui fut dirigé par un grandcardiologue, Nikolaï Amossov.