В годы правления преемников Юстиниана – Юстина II (565–578 гг.) и Маврикия (582–602 гг.) византийская благожелательная политика по отношению к Херсонесу продолжалась. Управление полуостровом перешло в руки дукса – ставленника Византии, резиденция которого располагалась в Херсонесе.

Хотя в конце V в. Херсонес окончательно потерял автономию и стал частью наследовавшей Риму Византийской империи, после падения античной цивилизации он просуществовал еще около тысячи лет и вошел в историю как центр восточного христианства.

Более того, в последующие столетия он выступает как влиятельный политический центр Византийской империи, становящийся подчас оплотом оппозиции и соперником самой столицы в борьбе за власть в империи.

В 695 г. император Византии Юстиниан II, позже получивший прозвище Риномет – Безносый – был свергнут его же полководцем Леонтием. Юстиниану сохранили жизнь, но публично изувечили (ему отрезали нос) и с позором отправили в ссылку в Херсонес. Такое наказание было достаточно типичным для политических преступников в Византийской империи. По-видимому, Херсонес, с одной стороны, был достаточно лоялен к византийской власти, с другой, находился достаточно далеко от центра империи.

Оказавшись в Тавриде, Юстиниан открыто заявил о своем желании вернуть утраченную власть, и принялся собирать союзников для своей борьбы.

В 698 г. в Константинополе произошел новый переворот, Леонтий был свергнут, и на его место встал Апсимар Тиверий III. Херсонеситы обратились к новому правителю с просьбой вернуть бывшего императора в столицу для повторного и окончательного суда.

Узнав об этом, Юстиниан, не дожидаясь ответа из центра, бежал, и укрылся в одной из крепостей, защищавших херсонеситов от кочевников, – Доросе (Мангупе), намереваясь в дальнейшем укрыться у хазар.

Караул в Мангупе в то время несли в основном федераты, готы и аланы, давно не получавшие жалования из Византии, и оттого не склонные к чрезмерной лояльности империи.

Отсюда Юстиниан связался с хазарами и потребовал встречи с каганом. Каган не только согласился поддержать опального императора, но также отдал ему в жены свою сестру, крещеную под именем Феодора, и разрешил поселиться в Фанагории, на восточном побережье Боспора.

Узнав о том, как сложилась судьба Юстиниана после бегства, Апсимар так же начал переписку с каганом, убеждая того выдать Юстиниана империи, или хотя бы прислать его голову. В обмен на сотрудничество он обещал кагану богатые дары. В 705 г., после некоторых раздумий, каган согласился, однако его решение не поддержала Феодора. Она выдала планы брата Юстиниану. Тогда беглец пригласил к себе убийц, нанятых каганом, якобы для простой беседы, и задушил их струной. Затем сразу же отплыл на запад, в бухту Символ (Балаклаву). Забрав там на борт своих союзников, он отправился дальше, на Дунай. Где обратился за помощью в борьбе с Константинополем к правителю Болгарии, сыну Аспаруха, хану Тервелю. В обмен на сотрудничество он обещал Тервелю богатые дары после победы и свою дочь.

В 706 г. при поддержке болгар Юстиниан вернул себе порфиру и приказал казнить обоих своих противников – Леонтия и Апсимара. Однако на этом он не успокоился. Чтобы отомстить Херсонесу и хазарам, Юстиниан снарядил военный флот и отправил его к берегам Тавриды под предлогом необходимости увести оттуда его жену. Однако флот попал в шторм, и большинство кораблей затонуло, не достигнув цели. Ответом на действия императора стало такое письмо к нему кагана: «О неразумный, неужели тебе было недостаточно двух или трех кораблей, чтобы забрать свою жену и не погубить столько людей? Или ты считаешь, что и ее возьмешь в сражении? Знай, у тебя родился сын, пошли (за ними) и возьми их». На сей раз Юстиниан последовал совету кагана и просто перевез в Константинополь Феодору и их сына Тиверия.

Однако через пять лет он повторил попытку, отправив в Таврику еще один флот с приказом не оставлять никого в живых, ни в Херсонесе, ни в соседних крепостях. Уничтожению подлежали даже те, кто оказывал поддержку Юстиниану в его бегстве.

Приказ был выполнен лишь частично. Херсон не оказал сопротивления. Византийцы казнили двадцать семь его протевонов, в городе учинили резню, позволив бежать только детям и подросткам. Еще 42 протевона, в том числе тудун – ставленник хазарского кагана – были в оковах отправлены в Константинополь.

Император остался недоволен милосердием исполнителей и осенью того же года отправил еще один флот, который опять погиб в буре. Однако Юстиниан не успокоился и тогда, приказав отправить еще одну карательную экспедицию.

На сей раз херсонеситы были готовы к нападению. В городе созрел заговор, который возглавил ставленник самого Юстиниана, глава Херсонесской администрации спарафий Илья и ссыльный знатный армянин Вардан, имевший прозвище Филиппик. Юстиниан, опасаясь последствий, изменил свои планы и отправил в Херсонес лишь небольшую эскадру с тремя сотнями воином на борту, целью которой было только захватить заговорщиков. В качестве знака расположения императора хазарам также были отправлены пленные: хазарский тудун и знатный протевон Зоил.

Однако херсонеситы на мировую не пошли. Они впустили в город руководителей экспедиции и заложников. Первых убили, а вторых вместе с остатками армии тут же передали хазарам. Тудун умер, так и не вернувшись в Хазарию, и все остальные пленники были принесены в жертву на его похоронах.

Противостояние Херсонеса с Константинополем тем временем продолжилось. Вардан провозгласил себя императором и объявил Юстиниана низложенным. Юстиниан в ответ отправил к берегам Тавриды еще одну карательную экспедицию под началом Патрикия Мавра. Приказ оставался прежним – стереть с лица земли мятежный город. Вардан стремительно бежал к хазарам. Херсонес оказался в осаде, и, возможно, пал бы, если бы в тыл атакующим не зашло войско хазар. Византийцы оказались блокированы с двух сторон и приняли решение перейти на сторону победителей.