Основание города относится к 212 году, но первые обитатели появились на этом месте еще в эпоху палеолита. В I тысячелетии до н. э. плато на скалистой конусообразной горе заселили тавры. Во II–III веках их сменили аланы – ираноязычные племена сарматского происхождения. Через столетие небольшой город перешел под управление византийского императора. Вместе с ромеями сюда проникло христианство, и, как следствие, за стенами крепости и в окрестностях начали строиться храмы и монастыри.
В первых веках надежно защищенное поселение Сугдея являлось окраиной античного мира. На пограничных землях Византии сходились торговые пути «из варяг в греки»; пересекались дороги из Европы, Египта, Малой Азии. Отсюда часто начинался длинный морской переход в Индию. В небольшом отдалении от города некогда находился античный порт Афинеон. Форт возвышался над 70-метровым обрывом на западных отрогах горы Караул-Оба. Неприступная цитадель с четырьмя башнями и бастионом принадлежала Боспорскому государству. Толщина стен местами достигала 3 метров. Французским словом bastion называли пятиугольное укрепление в виде выступа в углах крепостной ограды. Оно предназначалось для обстреливания местности спереди и вдоль крепостных стен и рвов.
Сугдейская крепость (ныне Крепостная) воздвигнута на южном склоне горы, некогда являвшейся коралловым рифом. Неприступная с юга и востока, в северной части она защищалась глубоким рвом. Сооружение имело два уровня обороны – нижний и верхний, между которыми располагались жилые кварталы. Второй ярус прикрывал цитадель; за пределами крепости раскинулись городские предместья. Перед Главными воротами с двумя башнями находился барбакан, как тогда называли полукруглую стену предмостового укрепления.
Оборонные постройки включали в себя массивные двухметровые в ширину стены высотой 6–8 метров и романские башни двух типов: закрытого и открытого (трехстенного). Большинство башен получили имена генуэзских консулов, по велению которых они строились. Указание на владельца вместе с датой постройки имеется на каждой башне. Например, башня Джиованни Марионе была закончена в 1388 году; башня Пасквале Джудиче – в 1392; башня де Флиско Лавани – в 1409. Настенные латинские надписи дополнены геральдической символикой: гербами Генуи, правившего дожа и консула крымской Солдайи.
В течение нескольких веков крепость подвергалась нашествию кочевников. Сменяя друг друга, город захватывали, грабили и разоряли хазары, печенеги, половцы, турки, татары. В XIII столетии он входил в состав Золотой Орды. Новые хозяева взимали с жителей официальную дань и время от времени совершали разбойничьи набеги. В то же время формально Солдайя находилась в распоряжении представителей Венецианской республики. Более чем столетнее присутствие венецианцев сделало город значительным торговым центром, процветавшим, несмотря на регулярные набеги кочевников. Его слава распространилась далеко за пределы Крыма. Здесь встречались негоцианты из многих страны мира. В гавань свободно заходили чужеземные корабли; по сухопутным дорогам беспрерывно шли караваны в Среднюю Азию, Китай и Московию.
Процветающая Солдайя стала предметом спора истинных хозяев и воинственных торговцев из Генуи, которых не устраивало господство венецианцев на Чёрном море. В 1365 году генуэзцы внезапно напали на Солдайю, приступом взяли крепость, захватив все окрестные поселения. Итальянские захватчики не собирались разрушать город, напротив, они достроили и реконструировали древние оборонительные сооружения, возвели новые стены, объединив крепость в единый ансамбль. При генуэзцах Солдайя утратила значение центра черноморской торговли, волей новых хозяев Крыма переместившегося в Каффу.
На скалистой вершине Крепостной горы до сегодняшнего дня возвышается Дозорная (Девичья) башня Кыз-Куле. Загадочная история этого сооружения вызвала рождение множества легенд, связанных с томившимися здесь узниками. Цитадель традиционно располагалась в верхнем ярусе и состояла из замка консула и нескольких башен, соединенных стеной, протянувшейся по самому гребню горы. Во время войны военачальник или комендант крепости не мог покинуть замок, поэтому в нем предусматривались помещения различного характера: от складов до роскошных покоев консула. Внутри крепости сохранились гидротехнические сооружения разных исторических периодов. В частности, итальянцы построили углубленную в землю прямоугольную цистерну и круглый бассейн для хранения питьевой воды. На территории цитадели находится единственный в Крыму готический храм.