Justinian's successors tried to hold on to North Africa, Italy, and Spain by establishing territories called exarchates ruled by governors known as exarchs; exarchates were military provinces in which civilian and military control were united. They held out in Spain until the 630s, Africa until the end of the seventh century, and Italy until 751, when a Germanic tribe called the Lombards captured it.
While the losses of territory in Europe were mourned by Byzantines at the time, they proved something of a blessing in disguise to the empire: with its territory limited to the Balkans and Anatolia, the smaller empire had much more coherent and easily-defended borders. Thus, those core areas remained under Byzantine control despite various losses for many centuries to come. The emperor Leo the Isaurian (r. 717 – 741) used themes-recruited soldiers to both fight off Arab sieges of Constantinople and to cement control of Anatolia. By the end of his reign, Anatolia was secure from the Arabs and would remain the major part of the Byzantine Empire for centuries.
In addition to the themes system, the empire added heavy cavalry to its roster and, famously, used a substance called Greek Fire in naval warfare; there are very few details, but it appears to have been an oil-based incendiary substance used to attack enemy ships. Finally, the empire made liberal use of spies and agents who infiltrated enemy governments and bribed or assassinated their targets to disrupt, or to start, wars.
In the Balkans, Slavic tribes proved a major ongoing problem for the Byzantines. A people known as the Avars invaded from the north in the sixth century and raided not just the Balkans but all across Europe, making it as far as the newly-created Frankish kingdom in present-day France. In the eighth century an even more ferocious nomadic people, the Bulgars (for whom the present-day country of Bulgaria is named), invaded. While the Avars had converted to Christianity during the period of their invasions, the Bulgars remained pagan. They destroyed the remaining Byzantine cities in the northern Balkans, slaughtered or enslaved the inhabitants, and crushed Byzantine armies. In one especially colorful moment in Bulgarian history, the Bulgar Khan, Krum, converted the skull of a slain emperor into a goblet in about 810 CE to toast his victory over a Byzantine army. Fifty years later, however, another Khan, Boris I, converted to Christianity and opened diplomatic relations with Constantinople.
This was an interesting and surprisingly common pattern: many "barbarian" peoples and kingdoms willingly converted to Christianity rather than having Christianity imposed on them through force. The Bulgars were consistently able to defeat Byzantine armies and they occupied territory seized from the Byzantine Empire, yet Boris I chose to convert (and to insist that his followers do as well). The major reason for this deliberate conversion revolved around the desire on the part of barbarian kings to, simply, stop being barbarians. Most kings recognized that Christianity was a prerequisite to entering into trade and diplomatic relations with Byzantium and the Christian kingdoms of the west. Once a kingdom converted, it could consider itself a member of the network of civilized societies, carry out alliances and trade with other kingdoms, and receive official recognition from the emperor (who still wielded considerable prestige and authority, even outside of the areas of direct Byzantine control).
An important figure in the history of eastern Christianity was St. Cyril, who in the ninth century created an alphabet for the Slavic languages, now called Cyrillic and still used in many Slavic languages including Russian. He then translated Greek liturgy into Slavonic and used it to teach and convert the inhabitants of Moravia and Bulgaria. Monasteries sprung up, from which monks would go further into Slavic lands, ultimately tying together a swath of territory deep into what would one day be Russia. The success of these missionary efforts united much of Eastern Europe and Byzantium in a common religious culture - that of Eastern Orthodoxy. Thus, up to the present, the Greek, Russian, Ukrainian, and Serbian Orthodox churches all share common historical roots and a common set of beliefs and practices.
The origins of Russia emerged out of this interaction, and out of the relationship between Byzantium and the Viking kings of the Slavs in Russia. Originally, the “Rus” were Vikings who ruled small cities in the vast steppes and forests of western Russia and the Ukraine. They were united in about 980 CE by a king, Vladimir the Great, who conquered all of the rival cities and imposed control from his capital in Kiev. He converted to Orthodox Christianity and forbade his subjects to continue worshiping Odin, Thor, and the other Norse gods. Just as Boris of Bulgaria had a century earlier, Vladimir used conversion to legitimize his own rule, by connecting his nascent kingdom to the prestige, power, and glory of ancient Rome embodied in the Byzantine Empire.