Первоначально поселение находилось на приморской полосе у подножия горы Крепостной (пляж совр. поселка Уютного). В 1968 г. археологи исследовали в этом месте так называемое Приморское укрепление, защищавшее поселение с моря. Укрепление датируется VI веком, однако эта датировка вызывает споры. Архитектор Е. И. Лопушинская считает, что архитектура и кладка сооружений характерны для более ранних - римского или раннехристианского периодов истории архитектуры (III - V века). На дне бухты подводники обнаружили позднеантичные предметы, что косвенно подтверждает более раннюю датировку.
Возникновение города и его название - Сугдея связывают с аланами. Это ираноязычные племена сарматского происхождения, предки современных осетин, которые появились в Крыму во II - III веках н. э. В. Г. Васильевский показал, что в языке осетин имеются слова "сугдед" и "сугдаг", а на Кавказе существует заброшенное поселение Суадаг. Ученый-топонимист В. Миллер предполагал, что название Сугдея происходит от ираноязычного слова "Сугда", что переводится как "непорочный", "святой". Швейцарский путешественник и ученый Дюбуа де Монпере и другие исследователи считали Судак главным портом аланов.
Впервые в литературном тексте Сугдея упоминается в "Космографе" VII века неизвестного автора из Равенны. В числе других городов северного побережья Чёрного моря назван город Согдабон и указано его примерное местонахождение. С этого времени различные письменные источники упоминают город постоянно.
Под властью Византии
Начиная с VI века, побережье Крымского полуострова от Херсона (средневековое название Херсонеса) до Боспора оказалось под властью Византии. При императоре Юстиниане I (527 - 565), проводившем активную внешнюю политику, в Таврике развернулось интенсивное крепостное строительство. На Южном берегу возводятся крепости Алустон (совр. Алушта) и Горзувиты (Гурзуф). Согласно архитектурному анализу самые ранние кладки стен крепости в Судаке на северном склоне Крепостной горы также относятся к VI веку. Крепостные стены нижнего оборонительного пояса существовали уже в VIII - IX веках. Расположение крепостных стен этого периода указывает на то, что в VI веке город, кроме прибрежной полосы, занимал почти ту же территорию на северном склоне горы Крепостной, границы которой и сейчас обозначены оборонительными сооружениями. В позднее средневековье город только несколько расширился на восток и на запад.
В середине VIII века произошел значительный прилив византийских греков на Крымский полуостров. В Византии в это время разгорелась ожесточенная борьба между иконоборцами и иконопочитателями. После победы иконоборцев, поддержанных императорской властью, иконопочитатели вынуждены были искать спасения на окраинах государства, в том числе и в Таврике. Здесь они основали большое количество церквей и монастырей, способствуя этим быстрой христианизации местного населения.
Хазары
В VIII - IX веках Крымом владели хазары. Сугдея стала их административным центром. В городе находился наместник хазарского кагана - тудун. Одновременно Сугдея являлась центром православной епархии (церковного округа) во главе сначала с епископом, а с Х века - архиепископом.
С вторжением хазар на Крымский полуостров здесь погибли многие византийские поселения. В Отузской и Коктебельской долинах обнаружены 15 византийских поселений, возникших в иконоборческую эпоху в первой половине VIII века и погибших в результате разгрома практически одновременно в том же VIII веке.
Были сожжены и византийские постройки Сугдеи. Несмотря на разгром, вокруг города продолжается консолидация христианского населения. Возник новый центр православия в Таврике - Сугдейская епархия. В VIII - IX веке усилилось византийское строительство на окраинах Судакской долины.
Со второй половины IX века началось строительство хазарских укреплений Сугдеи. Оборонительные стены толщиной 2,7 метра ограждали территорию площадью более 20 га, а значит, Судак в то время был крупным приморским городам. За стенами же находились лишь небольшие хижины, редко разбросанные по прилегающей местности. Взрослое мужское население крепости по численности, вероятно, не могло составить значительную военную силу, достаточную для защиты крепостных сооружений. Можно предположить, что в мирное время в крепости находился хазарский военачальник с регулярным войском, а во время войны сюда стекались отряды родовых вождей со всей территории Крымской Хазарии, а также - в случае крупных военных действий в Таврике - основные силы каганата. Таким образом, крепость в Судаке играла роль хазарского военного форпоста.
О численности хазарских войск в Сугдее можно предполагать, исходя из ранга постоянно находившегося в крепости хазарского наместника, известного по "Житию" Стефана Сурожского под именем Юрия Тархана. Тархан у тюрок являлся крупным военачальником, подчиненным только командующему войсками и кагану. Самым крупным подразделением в тюркском войске был тумен, состоящий из 10 тысяч всадников. Сугдея, во главе которой стоял тархан, предназначалась для развертывания хазарского тумена.
Крушение хазарского каганата связано с восточным походом князя Святослава в 965 г., когда были разгромлены основные силы хазар в Поволжье, на Дону и Северном Кавказе. Следствием этого похода была попытка Руси закрепиться на Боспоре Киммерийском и установить контроль над обоими берегами Керченского пролива. Воспользовавшись победами Святослава, Византия изгнала хазар из юго-западной Таврики, а в 971 г., после поражения Святослава в русско-византийской войне, влияние Византии было восстановлено на востоке Крымского полуострова и в Тамани. Вернув себе Сугдею, византийские императоры развернули здесь интенсивное строительство крепостных укреплений.
Печенеги, половцы
После освобождения Крыма от власти хазар в степях полуострова установилось господство печенегов. Впервые печенеги появились в Крыму в 882 г. К середине Х века они заняли почти весь полуостров, разгромив большинство селений, жители которых ушли в горы. Сугдея, несмотря на ущерб, причиненный печенегами, продолжала существовать как довольно значительный город.
В Х - XI веках Сугдея несколько раз упоминается в константинопольских церковных актах. В 997 г. определение константинопольского синода в числе других подписал архиепископ Константин Сугдейский. В 1026 г. в синоде участвовал архиепископ Сугдеи Арсений. В 1087 г. на церковном соборе присутствовал сугдейский архиепископ, имя которого осталось неизвестным.