A policy of ‘state Christianisation’ persisted into the seventh century. Heraclius converted a ‘Hunnic’ leader in 619 and Caucasian Albania in 628.27 Not until the ninth century do we hear of any further centralised initiatives on the part of the imperial authorities to convert distant barbarian tribes.28 Yet this very decline created substantial scope for local and personal initiatives of a kind which had perhaps existed before, but which the large-scale state ventures had overshadowed. Apart from cursory allusions to certain exiles who carried out pastoral work in the Crimea and Khazaria,29 we have the Life of Stephen, bishop of the Crimean city of Sougdaia. The Greek version of this Life is very brief, although slightly fuller versions exist in Slavonic and Armenian. Stephen was born in Cappadocia and received his bishopric in Sougdaia. The establishment of an episcopal see at a place like Sougdaia, on the edge of the barbarian world, is noteworthy in itself, since the town had only been founded in the later seventh century. Sougdaia was home to pagans (Khazars and Circassians) as well as Christians, and Stephen was an active preacher: ‘When the pagans heard that he worked wondrous miracles, they believed in the Lord, and a countless multitude was baptised. And he appointed many presbyters and deacons for them.’30 The missionary had established good relations with the local Khazar commander (the tarkhan), who ‘while exercising his power would regularly come to St Stephen and would listen and do as [Stephen] told him. And the saint instructed him much on the path to salvation.’31 Stephen died in office at the end of the eighth century. In the second quarter of the seventh century, a new and fearsome enemy appeared on Byzantium’s eastern borders: the Islamicised Arabs. Preaching Christianity to them directly was difficult in the extreme, except in the case of prisoners-of-war. Yet already by the eighth century we find instances of Arabs voluntarily converting to orthodoxy, as in the Life of Stephen Sabaites.32 What we have here, for the most part, is the apostasy and subsequent reconversion of Christians who had accepted Islam while in Arab captivity. One of the preachers to such people was Romanos the Neomartyr, executed in 778.33 According to the legendary Life of Theodore of Edessa, who most likely lived between 776 and 856, this bishop baptised none other thanMu‘awiya, ‘caliph of Baghdad’, at the caliph’s own request! Another missionary among the Arabs was Elias the Younger, a Sicilian who was shipped off to North Africa in the mid-ninth century.34 All these missionaries preached at their own risk. They would never have counted on support from Byzantium. The system of bishoprics in theBalkans virtually collapsed with the incursions of the Slavs. The Byzantine reconquest began in Greece in the eighth century and was followed by the Christianisation of the Slav groupings that had settled there. The Chronicle of Monemvasia relates how Emperor Nikephoros I ‘concerned himself with rebuilding churches and with turning the barbarians themselves into Christians’.35 The emperor’s methods are interesting: ‘He installed [the fugitive inhabitants of Patras] where they had been before, together with their own pastor . . . and he offered Patras the status of a metropolitanate . . . Therefore the barbarians, too,were instructed in the faith and baptised, and they joined the Christian faith.’36 The chief prerequisite for the baptism of the barbarians on reconquered imperial lands was thus the organisation of a network of bishoprics.