Переговоры Юстиниана с каганом привели их к полному соглашению. Бывший император убедил кагана в солидности своих прав и основательности надежд на возвращение престола. Юстиниан породнился с каганом браком, женившись на его сестре, носившей христианское и громкое в империи имя Феодоры. Претенденту предоставлено было жить в Фанагории, откуда он мог поддерживать сношения с недовольными существующим правительством в Константинополе. Но ему предстояло впереди испытать еще много неожиданностей. Тогдашний царь Тиверий III был встревожен дошедшими до него известиями и послал к кагану посольство с дарами и настоятельной просьбой выдать ему Юстиниана живым или мертвым[66]. Каган не остался глух к дарам и делаемым обещаниям и распорядился, чтобы за Юстинианом учрежден был тайный надзор. Вместе с тем поручено было правителю Фанагории и начальнику Боспора принять меры к убийству Юстиниана. Намерения кагана и сделанные им распоряжения сделались известны Феодоре, которая посвятила в них своего мужа и дала ему возможность избежать угрожавшей опасности.
Здесь начинается новая фаза приключений Юстиниана. Убив сам тех лиц, которые следили за ним, и оставив свою супругу на попечение тестя, Юстиниан устроил тайное бегство из Фанагории на заготовленном заранее корабле и с теми приверженцами, которые у него оказались в то время, пошел вдоль южного берега Крыма до гавани Символа (Балаклава), где вошел в сношения с преданными ему и очевидно сочувствовавшими задуманному им предприятию людьми в Херсоне. Все эти подробности должны быть хорошо взвешены, ибо они объясняют, что у Юстиниана была партия, которая обеспечивала ему успех в его замысле. Как можно понять из дальнейшего, Юстиниан, потеряв надежду на хазар, рассчитывал теперь найти союзника в другом месте. Из Херсона он направился вдоль северо-западного побережья Черного моря к устьям Дуная и нашел здесь гостеприимство у хана болгарской орды, еще весьма недавно переселившейся за Дунай и начавшей устраиваться на Балканском полуострове, по имени Тервель.
Хотя не все еще выяснено в обстоятельствах утверждения болгар за Дунаем, но весьма вероятно, что главный болгарский стан тогда уже был на месте нынешней деревни Абобы, близ Шумлы и Преславы[67]. Ханы болгарской орды, распространившие свою власть над славянами, жившими на север от Балкан, делали уже неоднократную попытку утвердиться и на юг от Балканских гор и зорко следили за событиями в империи, которыми всегда пользовались для своих набегов в имперские области. Как показывают древнейшие памятники болгарского быта, найденные при раскопках их древней столицы, болгаре скоро подчинились культурным влияниям, идущим из Константинополя, и ханы их постепенно вводили при своем дворе обычаи и обряды византийского двора.
Юстиниан мог быть заранее уверен в благорасположенном приеме хана Тервеля, т. к. последний хорошо мог оценить представляемые в деле восстановления Юстиниана на троне важные выгоды. Посланный для переговоров с Тервелем некто Стефан поставил вопрос так ясно и столько надавал обещаний болгарскому властителю, предлагая скрепить союз даже браком Тервеля с дочерью Юстиниана, что план похода на Константинополь с целью восстановления на престоле сверженного императора решен был без колебаний. Юстиниан был принят в болгарском стане с большими почестями и провел между болгарами осень и зиму 704/05 г. Весной предпринят был поход на Константинополь, в котором вместе с болгарами принимали участие и подчиненные им славяне. Из хода дел ясно, что правительство не приняло никаких серьезных мер против Юстиниана и его союзников. Без всякого сопротивления болгаре дошли до стен Константинополя и три дня стояли под стенами в ожидании сдачи города, в котором была значительная партия приверженцев последнего представителя дома Ираклия. Хотя открытой сдачи не последовало, но Юстиниан с немногими воинами нашел возможным тайно ночью проникнуть в город через водопровод, и тогда сопротивлению положен был конец. Трудно понять на основании скудных известий, почему так легко досталась Юстиниану победа. Если предположим, что город был взят на щит болгарами, то необходимо последовали бы расхищение сокровищ и отчаянная борьба между победителями и побежденными. По ходу событий нужно допустить, что Юстиниан, открывши доступ через водопровод, не сдал города Тервелю, а нашел возможным достигнуть власти без большого сопротивления, не позволяя болгарам сделаться хозяевами положения.