По приказу Юстиниана на южном берегу Крымского полуострова была создана мощная оборонительная система, включающая несколько опорных пунктов. Основными узлами обороны были построенные византийцами крепости Алустон (Алушта), Горзуиты (Гурзуф) и укрепленный пункт в Симболоне (Балаклава). В конце VI века у Судака существовало византийское береговое укрепление. Византийский историк Прокопий Кесарийский писал: «Что касается городов Боспора и Херсона, которые являются приморскими городами на том же берегу Эвксинского Понта за Меотидским болотом, за таврами и тавроскифами, и находятся на краю пределов римской державы, то, застав их стены в совершенно разрушенном состоянии, Юстиниан сделал их замечательно красивыми и крепкими. Он воздвиг там и два укрепления, так называемое Алуста и в Горзубитах. Особенно он укрепил стенами Боспор; с давних времен этот город стал варварским и находился под властью гуннов; император вернул его под власть римлян. Здесь же, на этом побережье есть страна по имени Дори, где с древних времен живут готы, которые не последовали за Теодорихом, направлявшимся в Италию. Они добровольно остались здесь и в мое еще время были в союзе с римлянами, отправлялись вместе с ними в поход, когда римляне шли на своих врагов, всякий раз когда императору было это угодно. Они достигают численностью населения до трех тысяч бойцов, в военном деле они превосходны, и в земледелии, которым они занимаются собственными руками, они достаточно искусны; гостеприимны они больше всех людей. Сама область Дори лежит на возвышенности, но она не камениста и не суха, напртив, земля очень хороша и приносит самые лучшие плоды. В этой стране император не построил нигде ни города, ни крепости, так как эти люди не терпят быть заключенными в каких бы то ни было стенах, но больше всего любили они жить всегда в полях. Так как казалось, что их местность легко доступна для нападения врагов, то император укрепил все места, где можно врагам вступить, длинными стенами и таким образом отстранил от готов беспокойство о вторжении в их страну врагов».
В Западной части Причерноморья в этот период утвердились новые пришельцы – большой племенной союз тюркоязычных племен – авары (в pусских летописях обpы), образовавшие Аварский каганат. Племена вар и потомки сарматов хиониты, жившие к северу от Аральского моря, к 558 году были разбиты тюркютами или тюрками – новым народом, возникшим при ассимиляции небольшого племени «семейства князя Ашина», ушедшего с территории северного Китая, и происходивших от хуннов алтайских племен. Перейдя Волгу, слившись в единый народ – авар, вары и хиониты расселились в степях Северного Причерноморья. К 565 году авары расширили свою территорию до Предкавказья, Дона и Кубани, овладели Паннонией и долиной Тиссы, совершали походы в Центральную Европу. Могущество авар начало падать после неудачной для них войны с Византией 626 года и в конце концов Аварский каганат был разгромлен войсками Карла Великого в 796 году и c 809 года являлся его вассалом. В V и VI веке авары совершали набеги на Крымский полуостров, частично оседая в Крыму.
Вслед за аварами в северно-причерноморских степях расселились тюрки– тюркюты, в середине 70-х годов VI века появившиеся в устье Кубани. Тюрки, как и персы, в то время воевавшие с Византией, хотели установить контроль над караванной дорогой из Китая в страны Передней Азии, Средиземноморья и Европы – «Великим шелковым путем», для контроля торговли шелком, ценившимся тогда на вес золота. В 567 году отряды тюрок во главе с Турксанфом, пройдя через Керченский пролив, захватили крепость Боспор, возникшую на месте бывшей столицы Боспорского царства Пантикапея. Имея плацдарм в Крыму, в 581 году войска тюрок попытались взять Херсонес, однако неожиданно сняли осаду и ушли из Крыма – в каганате тюрок, располагавшемся на территории нынешней Туркмении, началась гражданская война. В 590 году военный начальник Херсонской провинции Византии дука стратилат Евпатерий восстановил в Боспоре власть Византии.
Присутствие гуннов в Северном Причерноморье, продолжавшееся около ста лет, сменилась болгарским – племенами тюрской языковой группы, сначала подчинявшимися гуннам. Древние предки болгар кутургуры и утургуры в VI веке жили в низовьях Днепра, Дона и в бассейне Кубани, постоянно враждуя между собой. К середине VII эти племена обьединились, образовав болгарский народ. Обьединивший болгар Кубрат получил от византийского императора Ираклия сан патрикия и стал союзником Византии.