Постепенно власть Византии над Херсонесом укрепляется, здесь размещается византийский гарнизон. Отношение Херсонеса к империи в этот период носило противоречивый характер. Город был заинтересован в тесной экономической связи с Византией, большое значение имела военно-строительная деятельность византийской администрации города, которая защищала его от многочисленных врагов. Немаловажное значение имели и этническое родство, и единство языка, и культурная общность. Поэтому, несмотря на то, что Херсонес стремился к большей самостоятельности, вместе с тем, конечно, он не был заинтересован в разрыве с Византией. Зависимость Херсонеса выражалась в том, что уже в конце V в. здесь находился византийский гарнизон, который содержался на местные средства; существовал викарат – учреждение, собиравшее с населения подати и торговые пошлины; византийская администрация объединяла военную и гражданскую власть. В конце V в. в городе началось большое крепостное строительство, указывающее на значение города в качестве византийского форпоста в Северном Причерноморье. Особенно обширное строительство крепостных стен велось в VI в., при императоре Юстиниане I; именно в это время была, вероятно, сооружена мощная береговая линия стен, усилены и надстроены остальные оборонительные сооружения в соответствии с византийской стеностроительной практикой того времени.
Херсонес становится центром относительно большого района оседлого земледельческого населения, занимавшего юго-западное нагорье Таврики. Город становится также и большим торговым центром. Здесь происходит обмен сельскохозяйственной продукции на ремесленные изделия, как местные, так и привозные сельскохозяйственные орудия, украшения, гончарные изделия. В этот период резко возрастает потребность Херсонеса в продовольствии – увеличивается население города, появляется византийский гарнизон и огромная армия строителей. Кроме того, часть продуктов вывозится в Византию.
Все это приводит к экономическому подъему, который особенно проявляется в VI в., город начинает вновь чеканить свою монету. Подъему экономики способствовала и общая благоприятная обстановка – определенное затишье, наступившее в VI в. в Северном и Южном Причерноморье.
Византийские правители сооружали крепости и на подступах к Херсонесу. Кроме того, по словам Прокопия, Юстиниан I построил два укрепления на южном берегу – Алустон (нынешняя Алушта) и в Горзувитах (нынешний Гурзуф). Оба города были крупными поселениями, преимущественно аланскими. В том, что Горзувиты по своему этническому составу были не греческим городом, убеждает их обширный могильник Суук-су. Горзувиты и Алустон приобрели значение стратегически важных византийских крепостей так же, как и Мангуп и Эски-Кермен. Эти крепости были призваны не только защищать византийские владения степняков, но и осуществлять цели внутренней византийской политики в Таврике – закреплять зависимость населения этого края от Византии и подавлять возможное его сопротивление.
Той же политической цели служили усиленная пропаганда и насаждение христианства среди населения Таврики. Уже в начале IV в. была основана Херсонская епархия, еще раньше христианство стало проникать на Боспор; в IV в. там уже существовала христианская община.
Но христианство принимала прежде всего социальная верхушка общества. Именно к этому кругу принадлежали Сваг и Фаиспарта, богатая христианская усыпальница которых, сооруженная в 491 г., открыта в Керчи. Зажиточным гражданам принадлежал и богатый некрополь IV в. в Херсонесе. Основная же масса населения еще долгое время продолжала оставаться языческой.
В V и особенно в VI веке пропаганда христианства в Таврике резко усилилась и приобрела для Византии значение важнейшей государственной задачи. Насаждение христианства требовало массового строительства храмов, крещален, на что византийские правители, как видно, не скупились. Вместительные храмы в форме базилик (удлиненных трехчастных зал) строились в огромном для того времени количестве: некоторые из них были отделаны мрамором и мозаикой. Храмы-базилики возводились во всех крупных поселениях края; они открыты раскопками на Мангупе, Эски-Кермене, в Партените (на южном берегу), в районе Боспора (в Тиритаке). Но больше всего храмов строили в Херсонесе – тогдашней «столице» Таврики.