Po zwycięskiej wojnie z Bułgarami i Słowianami przesiedlił kilkadziesiąt tysięcy tych ostatnich do Azji Mniejszej. Sprowadził z Cypru w okolice Kyzikosu wielu Cypryjczyków, co doprowadziło do zerwania pokoju z Arabami. Wojna, która wynikła z tego faktu, zakończyła się niepowodzeniem cesarstwa na skutek zdrady oddziału złożonego ze słowiańskich przesiedleńców.
Wygnanie W 692 cesarz zainicjował Sobór in Trullo, który wprowadził równorzędność między biskupem Rzymu a patriarchą Konstantynopola. Postanowienia te spowodowały opór biskupa Rzymu Sergiusza. Próba siłowego rozwiązania tego problemu doprowadziła do buntu garnizonu Rzymu i Rawenny przeciwko cesarzowi. Został obalony w 695, a po okaleczeniu przez rhinokopię (obcięcie nosa) wygnany do Chersonezu na KrymieConstance Head: Justinian II. of Byzantium, Madison 1972, S. 112f. Z obawy o swoje życie uciekł na dwór kagana Chazarów i ożenił się z jego siostrą, która przybrała greckie imię Teodora (ok. 702). Jednakże wpływy, drugiego z kolei, uzurpatora na tronie w Konstantynopolu – Tyberiusza Apsimarosa sięgały aż do państwa Chazarów. Władca chazarski był zaś gotów wydać cesarza za cenę dobrych stosunków z nowym władcą Rzymian. Ostrzeżony Justynian zdążył zbiec na dwór bułgarskiego władcy Terwela. Uzyskał od niego pomoc wojskową, z której pomocą wyprawił się na stolicę.