В 1379 г. Стефан направился в Москву к Герасиму, являвшемуся тогда наместником митрополита (главы церкви), "дабы получить от него благословение на ... доброе проповедничество" в Коми крае:
"И я либо научу и обращу в христианство пермян, либо сложу голову свою за Христа, и за веру, и за доброе проповедывание".
Герасим благословил Стефана и устроил ему встречу с великим князем Дмитрием (Донским), который также поддержал замысел Стефана, выдал ему охранную грамоту, что придало миссии Стефана особый авторитет.
   В том же 1379 г. Стефан в сопровождении охраны и обоза с книгами, церковной утварью, иконами и другими вещами прибыл к устью р.Вычегды. Вначале он крестил пермян на Пыросе (в районе современного г.Котласа), построил там небольшую церковь, а затем направился вверх по Вычегде, побывал у коми, живших на р.Вилядь и крестил их.
   На пути своем Стефан встретил немало сложностей. Часть пермян, "слыша проповедь веры христианской, ...пожелали веровать и креститься". Но многие коми "пожелали воспротивиться сему", и Стефан поначалу "много зла претерпел от неверных пермян: озлобление, ропот, брань, хулу, укоры".
   Действия Стефана вызвали недовольство немалой части местного населения.
Выразителем ее интересов стал Пам-сотник, в уста которого Епифаний вложил такие обращенные к Стефану слова: "Кто дал тебе власть сие творить? Кто послал тебя в землю нашу, чтоб надругался ты над нашими богами, и храмы их разрушил, ...и службу нашу и честь в грязь втоптал, и веру нашу искоренить хотел?"
Жителям Коми края Пам говорил: "Не слушайте Стефана, пришельца...из Москвы! Что хорошего быть может нам от Москвы? Не оттуда ли к нам тяготы идут, дани тяжкие, и насилия, и судьи, и соглядатаи, и караульщики?" А московским властителям "поступают ныне меха от охоты нашей. И...князья, и бояре, и вельможи мехами обогащаются, в меха одеваются и ходят, красуясь... Не от нашей ли охоты меха в Орду посылаются?.. И в Царьград, и к немцам, и в Литву, и в прочие города и страны...".

   Проповеднику угрожали смертью, "обступали его с двух сторон и кругом с дубинами и длинными палками, желая нанести...смертельные удары", а однажды попытались сжечь на костре. Не будь у Стефана предоставленной великим князем охраны, миссия его могла бы закончиться довольно быстро и без большого успеха.
   Трудности не отвратили Стефана от намеченной цели. В 1380 г. он и сопровождавшие его люди поднялись до устья Выми. Здесь, в самом центре Коми края, на пересечении водных путей и невдалеке от древней кумирницы, были построены церковь Благовещения Богородицы и кельи. Так было положено начало современному селу Усть-Вымь. Поселившись там, Стефан стал проповедовать православие среди часто посещавших кумирницу пермян. Церковь, которую он украсил "яко невесту добру", привлекала взоры странствующих и путешествующих. Язычники приходили сюда подивиться "красоте и доброте здания церковного", вступали со Стефаном в беседы.
История Республики Коми. Сыктывкар, 1996г.