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