Чаще всего инициаторами крещения становилась не Византия, а сами варварские правители, которые надеялись путем христианизации попасть в сообщество цивилизованных стран. После княжеского крещения в Константинополе команды клириков выезжали на место для обращения страны. Разумеется, их охраняла дружина князя. Данные о том, как именно строилась византийская миссия, весьма скудны. Язык миссии — также сложный вопрос. По всей видимости, греки не учили варварских языков, а использовали переводчиков из местных или привозных варваров. Такая институция, как миссионерская епископия без епископского центра, если и существовала в Византии, то была развита плохо. Обычному греческому монаху полагалась «верность месту», а путешествия с миссионерскими целями не приветствовались (ср. ниже).
Успехи в государственном распространении христианства длились до середины VII в. Последовавшие затем военные поражения Византии со стороны арабов и булгар, а также глубокий хозяйственный кризис привели к тому, что сил на централизованные зарубежные миссии не осталось. В этот период в Византии появляется новый для нее тип независимого миссионера–одиночки. Первым стал в VIII в. Стефан, епископ Сугдеи в Крыму, обращавший в христианство варварских завоевателей— хазар. Тогда же начинается постепенная христианизация славян, осевших на Балканах. Однако подлинный расцвет миссионерства средневизантийского времени приходится уже на следующий, IX в., когда, к примеру, появилось новое Житие апостола Андрея, рисующее его как подлинного индивидуального миссионера. При том что солунские братья Константин–Кирилл и Мефодий, «апостолы» славян, не были миссионерами в строгом смысле слова (мораване, к которым отправились учительствовать братья, к тому времени уже были крещены), тем не менее их можно рассматривать как представителей самого «интернационалистского» крыла византийской культурной элиты. Но хотя в целом появление таких людей в Византии IX в. нельзя считать случайным — тем не менее их «интернационализм» зачастую предстает в современных исследованиях несколько внеисторично. Константин твердо верил в то, что крещения достойны все народы и что все языки равно созданы Богом, однако это не значит, будто для него понятие ‘варвар’ было нерелевантно. В том единственном тексте, который был записан явно со слов самого Константина, латиноязычном письме Анастасия Библиотекаря (в передаче Митрофана Смирнского), варвары представлены вполне трафаретным образом: Константин пытался разузнать в окрестностях Херсона, где находится могила Климента Римского, «но поскольку все тамошние жители были не местными, но пришельцами из разных варварских племен, да и вообще жестокими разбойниками (immo vero saevi latrunculi), они уверяли, что не знают, о чем он говорит»