Господство гуннов в Крыму продолжалось до середины VI в. С конца V в. на Крым начала распространять свое влияние Византийская империя. В 518 г. Византия подчинила себе территорию бывшего Боспорского царства, а к середине VI в. под её властью оказались значительные территории Южного Крыма, где началось усиленное оборонительное строительство. С конца V в. стали отстраиваться укрепления Херсонеса, а в середине VI в., при императоре Юстиниане, были сооружены крепости на Южном берегу – Алустон (Алушта) и Горзуваты (Гурзуф).

К IX-X вв. в Крыму окончательно сложились феодальные отношения. С упрочением международных позиций Византийской империи Крым опять попал в сферу её интересов. Этому способствовали разгром Хазарского каганата древнерусским государством и изгнание хазар из Крыма, где еще в 30-х годах IX в. была учреждена византийская Херсонская фема (провинция). В X в. Крым попал также в сферу влияния древнерусского государства. Восточные земли Крыма вошли в состав Тмутараканского княжества, в крупнейших центрах Крыма Херсонесе – Корсуни и Судаке – Суроже усилилось политическое и экономическое влияние Руси.