Но в этот момент в Константинополе произошел новый переворот.
Изгнанный в Херсон Юстиниан не оставил надежды вернуться на престол. Он бежал к хазарскому хакану, сумел привлечь его на свою сторону, женился на его дочери и стал готовить выступление против Алсимара. Тот потребовал от хакана выдачи Юстиниана, живым или мертвым. Хакан послал убийц, но Юстиниан, заблаговременно предупрежденный женою, расправился с ними и бежал из Хазарии по морю к болгарам. Феофан рассказывает характерный анекдот: случилась буря, суеверные моряки требовали, чтобы Юстиниан поклялся простить своих противников, — они думали, что тогда Бог сжалится и утихомирит бурю. А Юстиниан поклялся, что не оставит в живых ни одного из своих врагов.
Благополучно прибыв в Болгарию, Юстиниан сумел привлечь на свою сторону болгарского хана Тервеля и с болгарским войском подступил в 705 году к Константинополю. Юстиниан сам сумел проникнуть в город через подземный ход, вслед за ним ворвались войска. После победы болгары отошли от города, получив большие подарки.
Население Константинополя бурно приветствовало Юстиниана. Легкость переворота, сопровождавшегося гибелью многих знатных лиц, объясняется острой борьбой между плебсом и знатью и в то же время относительной слабостью столичного патрициата.
Репрессии Юстиниана были направлены и против городского патрициата, и против командного состава фемного войска.
Продолжалась борьба и с внешними врагами. Юстиниан, не имея возможности содержать многочисленную регулярную армию, посылал сражаться плохо вооруженные ополчения из ремесленников и крестьян, которые терпели поражения на суше и на море. Начатая война с арабами была очень неудачной. Положение в Италии стало шатким. Равенна, подозреваемая в мятеже, была разгромлена Юстинианом с невероятной жестокостью. Но с римским Папой Юстиниан решил заключить соглашение, надеясь таким образом укрепить положение византийцев в Италии. В конце 710 года Папа был торжественно принят в Константинополе в ущерб самолюбию константинопольского духовенства.
В это время жители Херсонеса, опасаясь политики Юстиниана, направленной против городского самоуправления, вступили в переговоры с хазарским хаканом, который направил в Херсонес своего наместника Юстиниан послал карательную экспедицию во главе с патрикием Стефаном и велел ему истребить мечом всех жителей Херсонеса.
Римляне, прибыв в город, захватили крепость, пленив хазарского наместника и уничтожив большую часть населения. Стефан оставил в городе архонтом спафария Илью, а сам погрузился на корабли и отплыл назад, но по пути флот его попал в бурю и почти весь затонул.