Due to Constantine IV's victories, the situation in the Eastern provinces of the Empire was stable when Justinian ascended the throne. After a preliminary strike against the Arabs in Armenia, Justinian managed to augment the sum paid by the Umayyad Caliphs as an annual tribute, and to regain control of part of Cyprus. The incomes of the provinces of Armenia and Iberia were divided among the two empires. Justinian signed a treaty with the Caliph Abd al-Malik ibn Marwan which rendered Cyprus neutral ground, with its tax revenue split.

Justinian took advantage of the peace in the East to regain possession of the Balkans, which were before then almost totally under the heel of Slavic tribes. In 687 Justinian transferred cavalry troops from Anatolia to Thrace. With a great military campaign in 688–689, Justinian defeated the Bulgars of Macedonia and was finally able to enter Thessalonica, the second most important Byzantine city in Europe.