Предположительно, древнейшее поселение на месте Старого Крыма называлось Кареа или Кареон (VI-III века до н.э. - первые века нашей эры). Древнегреческий географ Птолемей упоминает эти места под именем Таз. Однако все попытки локализовать на месте Старого Крыма древнегреческие города, сведения о которых туманны, а местоположение неясно, — довольно проблематичны. Зато более-менее определенно можно сказать, что города здесь не было до XII века, только поселение (по-половецки Суркат или Солхат; первое письменное упоминание о нем относится к 1266 году).

Название Солхат в разных формах встречается в еврейских (X—XVI века), армянских (XIV век), итальянских (XIII—XIV века) и испанском (XV век) письменных источниках. Пять форм топонима "солхат" насчитывается в исторической хронике „Сельджук-наме", созданной в XIII веке. На китайской карте 1331 года город обозначен как Сагила (Солгат). Арабские средневековые источники называют город ал-Кирим. В средневековых армянских рукописях встречается название Сурхат. Татары называли город Крым.

До настоящего времени вызывает споры происхождение топонима "Солхат". По мнению А. Григорьева, в их основе лежат тюркские названия. Солхат по-тюркски означает „левая сторона". Поскольку слово "сол" у тюрков и монголов обозначает положение на местности, "Солхат" можно перевести как "Левое поселение". А. Григорьев считает, что левая сторона здесь "северная сторона Черного моря". Однако М. Крамаровский указывает: " Вероятно, ключ к расшифровке топонима — в реальном положении селения на местности: выбрав в линейной ориентации позицию в сторону восходящего солнца, слева от себя мы обнаружим юго-восточный склон горы Агармыш, завершающий с северо-востока Внешнюю крымскую гряду. Следовательно, топоним "Солхат" можно прочесть как "селение" (город) на левом склоне (крае) горы". По другой версии, Солхатом в те времена называли не весь город, а ту его часть, где проживали не мусульмане, а греки, армяне, генуэзцы. Армяне называли город Гин-Гримиц — то есть Старый Крым по-армянски. Этот народ имел здесь не просто вторую родину (армяне на полуострове появились с XIII века), но и духовный центр: в лесистых окрестных горах находилось несколько армянских монастырей, самые известные из которых Сурб-Хач и Сурб-Стефанос (Георгий).

Из археологических и письменных источников известно, что к XII веку на месте Старого Крыма возникает большой торговый центр с крепостными стенами и рвом (их остатки можно осмотреть на северо-восточной окраине города). За его стенами проживают греки, армяне, русские, потомки печенегов, половцев, хазар, аланов. Возвышению Солхата способствовали несколько причин. В средние века юго-восточный Крым превратился в один из центров международной торговли. В XIII веке в бассейне Черного моря вели торговлю итальянские купцы — венецианцы и генуэзцы. Главенствующее место среди генуэзских торговых факторий в Причерноморье заняла Каффа (современная Феодосия).

С другой стороны, на огромных просторах Европы и Азии в XIII веке возникло новое могущественное государство — Золотая Орда. Распространив свою власть на огромную территорию — от Китая до Черного моря, монголо-татары создали в ее пределах самую передовую по тем временам систему коммуникаций. Путь из Европы в глубины Азии стал удобным и безопасным. Караваны из Китая могли следовать в черноморские порты и Приазовье. Часть их направлялась в Солхат, который таким образом втягивался в международную торговлю. Естественным торговым партнером Солхата стала генуэзская Каффа. Солхат стал административным центром Крымского улуса Золотой Орды. Уже со второй четверти XIII века здесь пребывал нойон-военачальник, подвластный золотоордынскому хану.

Уже перед приходом ордынцев Солхат был значительным городом, который населяли греки, генуэзцы, армяне. Ордынцы, восприимчивые к чужой, более высокой культуре, потянулись к оседлости и развернули широкую строительную деятельность. Не имея собственного строительного опыта, вчерашние кочевники привлекли к строительству солхатских мастеров. Богатея, город ширился, укреплялся. Строились городские дома для знати и ремесленников, склады и лавки для купцов, постоялые дворы, фонтаны, обновлялись крепостные стены и башни. В 1253 году по приказу хана Батыя в Солхате для него был построен дворец.

Хотя, по словам Е. Катюшина, Каффа могла рассматривать Солхат как некое продолжение своего торгового причала, а последний мог видеть в ней собственный морской порт, взаимоотношения двух городов осложнялись серьезными внутренними противоречиями, которые иногда перерастали в прямые вооруженные стычки. Так, в 1307 году, не имея возможности противостоять натиску татар, жители Каффы покинули город, предварительно разрушив его. Жизнь в нем возродилась только через несколько лет, с разрешения хана Узбека.

В 1395 году Солхат был разрушен войсками Тимура (Тамерлана), а в 40-е годы XV столетия сыном золотоордынского хана Тохтамыша — Саиид Ахмедом. С этим же временем связано еще одно известное событие: убийство в городе темника Мамая в 1380 году. Этот военачальник, будучи женатым на дочери золотоордынского хана, стал фактическим владельцем западных улусов Золотой Орды, в том числе и Крымского улуса. Для утверждения здесь своей власти он организовал карательный поход на полуостров, разрушил много городов и селений, захватил аланское княжество Кырк-Ер (позже получило более известное название Чуфут-Кале). Стремясь помешать консолидации русских земель, Мамай нанес ряд ударов по русским княжествам, но при попытке вторжения в Московское княжество потерпел поражение в Куликовской битве 1380 года, после чего вскоре был разбит Тохтамышем, бежал в Кафу, затем в Солхат, где и был убит. Не помогли Мамаю и генуэзцы, ранее предоставившие ему деньги наемников для воцарения на золотоордынском престоле, и «неоправдавшем доверия».

После распада Золотой Орды и образования независимого Крымского Ханства ханская резиденция была перенесена в Бахчисарай. Слава Солхата быстро угасает. С провозглашением Хаджи-Гиреем себя крымским ханом в 1443 году, переездом его в Кырк-Ер, Солхат стал хиреть, генуэзцы перестали тут торговать. Удар по международной торговле нанесли и падение Византийской империи под натиском турок-сельджуков в 1453 году, и захват турками Кафы и других приморских городов полуострова спустя 22 года. Город получает название Эски-Крым (Старый Крым). Кырым в переводе с тюркского означает «ров, крепость». Возможно, от укреплений города позже получил свое название и весь полуостров.

Польский путешественник Мартин Броневский так описывает город, в котором он побывал в 1578 году: „Крем, или по-татарски Крым, город с крепостью, окруженный высокой и толстой стеной, совершенно отличается от других городов Средиземного Херсонеса (так называл его Птолемей) своей величиной и знаменитостью... видны еще храмы и святилища... не только в самом городе, но и вне города, украшенные халдейскими надписями, высеченными на больших камнях... Видно из развалин и обширности мест, что это был один из знаменитейших и величайших городов своего времени..."

Екатерина Великая в Старом Крыму

После присоединения Крыма к России Старый Крым получил новое название — Левкополь (Тихий город). Имперское правительство намеревалось сделать город столицей Таврической губернии. Однако столицей стал Симферополь, и хотя с 8 февраля 1784 года Старый Крым - центр Левкопольского уезда, уже 2 апреля того же года уездным городом стала Феодосия. Старый Крым на долгие годы остался заштатным городом.

В 1787 году состоялось путешествие в Крым Екатерины II, которое до сих пор остается самым знаменитым крымским путешествием. В свиту императрицы входили князь Потемкин, австрийский император Иосиф II, путешествовавший под именем графа Фалькенштейна, принц де Линь, граф де Сегюр, граф А. Безбородко и другие высокопоставленные лица. Екатерина II в сопровождении своей пышной свиты посетила Симферополь, Севастополь, Феодосию.

27 мая 1787 года в 2 часа пополудни Екатерина II выехала из Карасубазара (совр. Белогорск) и в седьмом часу прибыла в Старый Крым, где остановилась на ночлег в специально для этого построенном дворце. По прибытии императрицы легкоконный Таврический полк отдавал честь с преклонением штандартов, били в литавры и играли на трубах, с наступлением темноты сад и вся прилегающая к дворцу территория были иллюминированы.

На следующий день, 28 мая, императрица посетила Феодосию. При въезде в город, так же, как и при отбытии, была произведена пушечная пальба. Екатерина посетила Феодосийский монетный двор, где в ее присутствии были оттиснуты две золотые медали с обозначением года, месяца и дня. Потемкин преподнес эти медали Екатерине и графу Фалькенштейну. В свою очередь Екатерина вручила орден св. Владимира 3 степени бригадиру Шицу, командовавшему легкоконным Таврическим полком, в воздаяние его отличной и ревностной службы. В тот же день высокопоставленные путешественники вернулись в Старый Крым, где провели следующую ночь.

Интересна история дворца, построенного в Старом Крыму для Екатерины II. Изначально на его месте находилась армянская церковь, которую в преддверии будущего путешествия перестроили во дворец. Впоследствии дворец стал православным храмом во имя Успения Божьей Матери. В нем пребывали архипастыри Феодосийские и Мариупольские, а именно: Дорофей, скончавшийся в 1787 году в Таганроге, Моисей, погибший от рук злодеев, Иов, Гервасий и Христофор. После перевода последнего в Харьков преосвященных в Старом Крыму больше не было, а осталось только место приходского священника. Богослужение продолжалось до 27 января 1825 года, когда, вероятно, из-за неосторожности священнослужителей, церковь сгорела. В саду при храме, который еще долго сохранялся в Старом Крыму в виде развалин, находился памятник похороненному здесь двухлетнему сыну генерала Панчулидзева, а за оградой — памятник на месте захоронения полковника Донского казачьего войска Чикалева.

В Старом Крыму специально к приезду императрицы был построен так называемый Екатерининский фонтан. Это было сооружение в виде крытого черепицей павильона в восточном стиле. Сверху, над фонтаном, была сооружена беседка, где знаменитая гостья изволила пить чай. По прошествии времени фонтан был почти полностью разрушен

В конце XVIII века в окрестностях Старого Крыма пытались основать центр крымского шелководства, и местные условия для этого исследовал известный ученый К. И. Таблиц.