Языческій народъ, поселенія котораго прилегали къ Устюгу, составляли, принадлежавшіе къ финскому семейству народовъ, вычегодскіе Пермяне или Пермяки, получившіе потомъ и насъ особое имя Зырянъ (отъ одного изъ племенъ, которое у Епифанія называется Сырьянами). Этотъ народъ составлялъ половину Пермяковъ. Другую половину составляли Пермяки камскіе, область которыхъ называлась Великая Пермь. Главнымъ городомъ зырянъ было позднѣйшее селеніе Усть-Вымь, при впаденіи Выми въ Вычегду (около 350 вер. отъ Устюга). Туда направился Стефанъ и началъ тамъ проповѣдь. На первыхъ порахъ ей вняли немногіе. Большинство же старалось выпроводить проповѣдника. Дѣйствовать рѣшительно язычники все же опасались, зная, что за Стефаномъ стоитъ сильная Москва, данниками которой они тогда состояли (раньше были подъ Новгородомъ). Они старались выжить его своими страхованіями. Подъ предводительствомъ волхвовъ собирались они вокругъ его жилища, вооруженные кольями, и грозили убить его. Или обкладывали домикъ его хворостомъ и соломой, грозя сжечь святаго. Готовый потерпѣть за Христа и смерть, Стефанъ отвѣчалъ на страхованія усиленіемъ проповѣди и продолжалъ переводъ богослужебныхъ книгъ.
Въ Усть-Выми на холмѣ стояла невзрачная кумирня. Противъ нея на насыпномъ холмѣ Стефанъ воздвигъ великолѣпную деревянную церковь во имя Благовѣщенія Богородицы, освятивъ ее торжественно съ духовенствомъ, вызваннымъ изъ Устюга. Храмъ этотъ, кротость и ласковое обращеніе привлекали къ Стефану зырянъ, но мало кто рѣшался креститься. Надо было наглядно доказать то, о чемъ проповѣдывалъ святой — идолы суть мертвые обрубки дерева и чурбаны и, конечно, защитить себя не могутъ. Улучивъ время, когда въ кумирницѣ никого не было и она не была охраняема, Стефанъ поджогъ ее. Прибѣжавшіе разъяренные волхвы и кудесники бросились на него съ кольями и топорами, но отъ идоловъ остался одинъ пепелъ. Это быстрое обращеніе множества боговъ въ ничто и то, что боги не тронули ни единаго волоса на головѣ дерзновеннаго, поднявшаго на нихъ руку, произвело на народъ потрясающее впечатлѣніе. На пепелищѣ своей кумирни и какъ бы на пепелищѣ своего язычества, жители Усть-Выми собрались на сходъ рѣшать вопросъ: что имъ дѣлать. Горячая проповѣдь святого къ этому сходу убѣдила язычниковъ принять истиннаго Бога. Такимъ образомъ началось крещеніе зырянъ какъ цѣлаго народа. Одержалъ онъ побѣду и надъ главнымъ волхвомъ Памою. Кудесникъ самъ вызвался пройти, вмѣстѣ со Стефаномъ, сквозь огонь и рѣку подъ льдомъ (отъ проруби до проруби), чтобы испытать, чья вѣра сильнѣе. “Я не повелѣваю стихіями, но Богъ христіанскій великъ, — иду съ тобою” — сказалъ Стефанъ. Памъ затрепеталъ, отказался отъ испытанія. Огромная толпа едва не растерзала Пама. Этимъ довершилось торжество вѣры надъ суевѣріемъ. Народъ толпами крестился и бросалъ въ огонь идоловъ. Изъ среды крещеныхъ святой набралъ мужей, юношей и дѣтей, которые могли бы быть поставлены во священники и на прочія церковныя должности. Онъ обучалъ ихъ новоизобрѣтенной зырянской азбукѣ и совершенію службъ по своимъ зырянскимъ книгамъ. Поставилъ еще двѣ церкви. На одномъ холмѣ стояла большая береза, къ которой народъ имѣлъ великое благоговѣніе, какъ къ своего рода божеству (возможно, считая ее обиталищемъ боговъ). Дерево это, къ которому никто не смѣлъ приступиться, Стефанъ срубилъ собственноручно и поставилъ церковь такъ, чтобы пень дерева служилъ основаніемъ для ея престола. Со всѣхъ концовъ зырянской земли стекался въ Усть-Вымъ народъ, ища у святого научиться новой вѣрѣ и прося у него крещенія. Требовались и личныя путешествія Стефана, какъ для крещенія, такъ и для уничтоженія мѣстныхъ кумирницъ. Какъ всегда бываетъ при обращеніи язычниковъ, послѣдніе нѣкоторое время не перестаютъ питать страхъ къ своимъ прежнимъ богамъ и не дерзаютъ поднимать на нихъ собственныя руки, опасаясь ихъ мщенія. Приходилось уничтожать кумирницы самому Стефану. Совершая это, святой приказывалъ строить по погостамъ и селеніямъ церкви и опредѣлялъ къ нимъ священниковъ, которыхъ посылалъ въ Москву для поставленія.