To defeat these dangerous rebellions in Anatolia, Basil formed an alliance with Prince Vladimir I of Kiev, who in 988 had captured Chersonesos, the Empire's main base in the Crimean Peninsula. Vladimir offered to evacuate Chersonesos and to supply 6,000 of his soldiers as reinforcements to Basil. In exchange, he demanded to be married to Basil's younger sister Anna. At first, Basil hesitated. The Byzantines viewed all of the peoples of Northern Europe—namely Franks and Slavs—as barbarians. Anna objected to marrying a barbarian ruler because such a marriage would have no precedent in Imperial annals.

Vladimir had researched various religions, having sent delegates to various countries. Marriage was not his main reason for choosing Christianity. When Vladimir promised to baptize himself and to convert his people to Christianity, Basil finally agreed. Vladimir and Anna were married in Crimea in 989. The Rus' warriors taken into Basil's army were instrumental in ending the rebellion; they were later organized into the Varangian Guard. This marriage had important long-term implications, marking the beginning of the process by which the Grand Duchy of Moscow many centuries later would proclaim itself "The Third Rome", and claim the political and cultural heritage of the Byzantine Empire.