Византийские цитадели являют собой вершину военной мысли. Они охраняют все важнейшие стратегические проходы из степной части полуострова к Южному берегу: Каламита охраняет долину Чёрной речки; Дорос, Черкес-Кермен и Эски-Кермен — входы между Чёрной речкой и Бельбеком; Качи-Кальон и Тепе-Кермен—долину Качи; Чуфут-Кале — проходы между долиной Качи и долиной Чурук-Су; Бакла — проходы между Альминской и Бодракской долинами. Это гигантское строительство становится последней акцией подобного масштаба, осуществлённой Византией на дальних границах. После Юстиниана I подобный размах оказывается не по силам истощённому войнами государству, постоянно ведущему сражения как минимум на два фронта. Через некоторое время ликвидируется принцип федератства, прекращаются выплаты на содержание союзников.
Археологические раскопки показывают, что экономика средневековых городов Крыма в этот период тесно связана с Византией. В раскопках VI-VIII вв. прослеживается явное преобладание ремесленных изделий из прибрежных византийских центров над местными. Хождение имеют не только золотые и серебряные византийские монеты, являющиеся мировой валютой, но и бронзовые монеты, предназначенные исключительно для местного обращения. Очевидно, в это время или чуть позже византийцы привезли с собой в Таврику грецкий орех, инжир, виноград, фисташки. Некоторые могучие древние деревья, посаженные в те давние времена, живут и поныне, как бы смыкая эпохи — в Крыму часто теряется масштаб времени.
Во второй половине VIII в. начинается массовое переселение на полуостров выходцев из Византии. Империю раздирает гражданская война, вспыхнувшая на религиозной основе. «Иконопочитатели» по наставлению св. Стефана Нового переселяются в Крым, спасаясь от репрессий пришедших к власти «иконоборцев». С этим временем связано упрочнение христианской идеологии на крымской земле, возведение многочисленных православных храмов и монастырей.
Ведущей силой Степи в это время был Хазарский каганат, который в течение нескольких веков воевал с Византией. Хазары представляли собой весьма необычную этническую систему. В дельте Волги обитали аборигены, чьим основным занятием были охота и рыболовство, в степях кочевали тюркские племена, являющиеся олигархами каганата. В Итиле и других городах ремесла и торговля были в ведении большой иудейской общины. Главенствующей религией государства стал иудаизм. Основу военной силы каганата составляли наёмные войска, костяком которых были воинственные степные племена.

Воспользовавшись ослаблением Византии из-за раздирающих её междоусобиц, хазары прорвали оборонительную систему византийской обороны в Крыму и захватили пограничные крепости и центральную горную крепость Дорос. Однако они неожиданно встретили отчаянное сопротивление нового этноса, возникшего из слияния принявших христианство готоаланов и многонациональных выходцев из Византии. Объединившись под началом архиепископа Иоанна Готского, христиане Крыма захватили перевалы на дорогах и заняли крепость Дорос. Хазары жестоко подавили их сопротивление, многие поселения были преданы мечу и огню. Ещё более полувека местное население вынуждено было платить дань хазарским наместникам — тудунам. Но к началу X в. Византия вернула утраченный контроль над югом полуострова. Последний набег хазар датируется серединой X века.
Впрочем, отношения Византии, херсонитов и Хазарии нельзя трактовать как однозначное противостояние первых двух против каганата. С одной стороны, Херсон всегда тяготел к независимости, с другой стороны, Византия постоянно раскалывалась иа смертельно враждующие между собой лагеря. В 711-713 гг. выходец из Армении Вардан, отбывавший в Херсоне ссылку, был провозглашён херсонитами, хазарами и своими византийскими сторонниками басилевсом и правил Византией под именем Филиппика почти два года.
Затем Великая Степь представила на сцену противоборства со Средиземноморьем новые силы — осколки сарматских племен были объединены тюркоязычными племенами печенегов и половцев, отличающимися голубым цветом глаз и светлыми волосами, за что и получили свое славянское название. Себя половцы называют куманами, или кипчаками. Кочевники обосновываются в степном Крыму. Были ли их отношения с византийцами и херсонитами только враждебными или строились на основе торговых связей, до конца не выяснено. Скорее всего, имело место и то и другое.
У Византии в это время появляется новый противник-союзник. С севера совершают стремительные набеги викинги и союзные или подчинённые им племена славян. В X в. на Таманском полуострове ими основывается Тмутараканское княжество, обязанное своим названием столице, хазарское название которой «Таматарха» было переиначено на северный лад. Византиец Лев Диакон, рассказывая об отступлении князя Игоря из Византии, называет Боспор «родиной русских». В другом источнике говорится, что Святослав, скрываясь от преследования византийцев, уходит «в своё отечество — Боспор Киммерийский».

В 988 г. Великий князь Владимир, младший сын Святослава, вступает с Византией в сложную политическую борьбу. За поддержку царствующей династии против мятежников он требует руку дочери басилевса. Подобный союз должен быть скреплён церковным браком, и Владимир принимает в Херсонесе христианство и обязуется крестить Русь. На стороне Византии Владимир воюет с мятежниками и, как гласят летописи, разоряет Херсонес, еще 10 городов и 50 селений. На крымском берегу Керченского пролива строится крепость, и обе стороны этой стратегически важной водной артерии оказываются под контролем Руси. В 1068 г. при княжении в Тмутаракани Глеба Святославича был высечен камень с данными о ширине Керченского пролива, найденный на Таманском полуострове в 1792 году. В 60-70-х гг. XI в. в Тмутаракани жил летописец Никон, благодаря которому мы многое знаем об этом историческом периоде. Чёрное море на картах арабских географов в Х-ХII вв. именуется Русским.
Взаимоотношения византийцев со своими северными соседями носят крайне противоречивый характер, союзы «на вечные времена» чередуются с войнами, поочередно какие-либо две стороны объединяются против третьей. В XII в. под ударами половцев и византийцев Тмутаракань выходит из состава раздираемого междоусобицами Киевского княжества.
Тринадцатый век был для Крыма веком особенно тяжких исторических потрясений. Хотя в истории не может быть понятия «плохой» или «хороший», не следует забывать, что для участников исторических событий эти оценки весьма правомерны. Более того, они вполне вправе считать «плохими» целые исторические периоды, что нашло свое отражение в пословице: «Не дай нам Бог жить в интересные времена». В 1222 г. на полуостров из средиземноморской Анатолии вторгаются турки-сельджуки, тюркские племена, захватавшие значительные территории слабеющей Византии. Ешё через год на Крымский полуостров обрушиваются войска монголов. Поначалу ордынцы ограничиваются разорением торгового Судака, но в 1239 г. войска Батыя полностью покоряют Крым.