Стефан испросил у наместника московского митрополита благословения и отправился с христианской проповедью к язычникам.

Поначалу пермяне встретили Стефана недоверчиво и даже враждебно, чинили ему всяческое «хуление, укорение, досаждение, поношение и пакость», однажды обступили его «с ослопы, смерть ему нанести хотяше», в другой раз обложили сухой соломой, «умысливша огнем немилостиво в смерть вогнать его».

Епифаний Премудрый не рассказывает, каким образом удалось Стефану выйти живым из этих критических ситуаций. Возможно, миролюбивые по натуре пермяне были обезоружены неизменной кротостью Стефана. Епифаний вкладывает в их уста рассуждение о том, что если бы Стефан первым «дерзнул творити начало бьения», то его бы растерзали, но поскольку он «долготерпелив», они не знают, что можно «сотворити ему».

Постепенно мужество и добросердечие Стефана привлекли к нему сердца пермян. Они поверили в его благие намерения, стали слушать его проповеди, и некоторые согласились принять крещение. Так среди пермян появились первые христиане.

В Усть-Выми, месте, где река Вымь впадает в Вычегду, Стефан построил первую в Пермской земле христианскую церковь — «высоку и хорошу, красну и добру, чюдну вправду и дивну». Красота этой церкви немало способствовала делу обращения пермян в христианство. Некрещеные пермяне приходили к ней вместе с принявшими христианство «не молитвы ради, но видети хотяше красоты здания церковного». Любуясь церковью, они слушали проповеди Стефана и постепенно тоже проникались христианским духом.

Стефан полагал, что для успешного насаждения христианства необходимо уничтожить все принадлежности языческого культа. И он принялся разрушать древние языческие святилища. «Без боязни и без ужасти» ходил Стефан со своими новыми учениками по полям и лесам, отыскивал изображения древних богов, сделанные из дерева, «и обухом в лоб бьяше идола, и по ногам сокрушаше, и секирою ссечаше, и на поление раздробляйте, идо конца искореняше, и огнем сжегаше, и в пламени испепеляше».

Конечно, сейчас об этом остается только пожалеть. Один из исследователей фольклора коми, А.А. Попов, писал в 1930-х годах: «Вследствие такой ретивой его деятельности, мы не имеем никаких материальных памятников для воссоздания картины дохристианской религии коми». (К счастью, исследователь ошибся. В последующие годы археологами было найдено довольно много материальных памятников пермского язычества, в том числе так называемый «Гайнский идол». Вот как он описывается в книге Л.С. Грибовой «Декоративно-прикладное искусство народов коми»: «Мастер умело использовал свойства самого материала: два срезанных сука изображают круглые, как у филина, глаза. Они окружены кругами древесных волокон, создающих впечатление складок вокруг глаз, и, продолжаясь вверх и вниз, являются как бы морщинами старого лица. (…) впечатляющий образ идола свидетельствует о незаурядном мастерстве резчика, его несомненном художественном таланте».) Стефан же не думал, что разрушаемые им святилища имеют историко-культурную ценность, он действовал с верою и бескорыстно, считая, что совершает благое дело.

Как-то раз Стефан сжег и сравнял с землей очередную кумирницу — деревянное строение, в котором помещался идол. Епифаний особо отмечает, что никого при этом не было, но Стефан, «сотворив победу, не отбежал от места того», а сел и стал ждать, когда появятся язычники, «грядущие против него». Язычники явились, вооруженные топорами и кольями, и набросились на Стефана, но тот смог их успокоить разумными речами и даже произнес проповедь.

По языческому обычаю, пермяне приносили идолам богатые дары. В кумирницах было сложено много золотых и серебряных украшений, посуды, драгоценных мехов. Все это богатство Стефан, не жалея, предавал огню. Пермяне удивлялись: «Како не приимаше себе всего того в корысть?» Лишь однажды Стефан сохранил пелену, которой был украшен один из идолов, и отдал ее своему служке, принявшему христианство пермянину Матвейке. Стефан поступил так «не прибытка ради», а чтобы наглядно продемонстрировать бессилие языческих богов. Матвейка сшил себе из пелены штаны и ноговицы, остаток пустил на онучи и все это износил «без пакости и вреда для себя».

Из всех пермских языческих жрецов особым авторитетом у пермян пользовался волхв по имени Пам. Пермяне называли его своим учителем и считали, что его волхованием «управляется Пермская земля». Пам, «ненавидя веру христианскую», оказывал сильное противодействие Стефану, запрещая пермянам креститься, а уже окрестившихся убеждал снова вернуться к языческой вере.

Пам говорил пермянам: «Братья, мужи пермские! Не оставляйте отеческих богов, не покидайте старых обычаев, давней веры не забывайте! Слушайте меня, а не Стефана. Он пришел к нам из Москвы и для вас чужой, я же — вашего рода, одного с вами племени и языка и добра вам желаю. Больше подобает вам слушать меня, вашего старого учителя, а не пришлого чужеверца, который годится мне в сыновья, а то и во внуки!» Многим речи старого волхва казались убедительными. Стефан сокрушался: «Сколько я строю — столько он разоряет!» Стефан и Пам неоднократно спорили между собой, отстаивая преимущества своей веры, но каждый из них оставался непоколебимо уверен в собственной правоте и спор ни к чему не приводил, лишь распаляя обоих спорщиков. Епифаний Премудрый, безусловно разделяет точку зрения Стефана, тем не менее вполне объективно замечает: «Друг друга они не слушали, и один другого именовал неразумным».

Однажды зимой Стефан и Пам вели диспут о вере на берегу замерзшей реки Вычегды при большом стечении народа.

Стефан вопрошал Пама: «Скажи мне, окаянный, суемудрый старец, почему ты хулишь веру христианскую, благодаря которой темные были просвещены, заблудшие — разысканы, погибшие — спасены, и десятки тысяч благ сотворились? Что может быть лучше, чем служить живому Богу? Небо и земля полны славой Его! Он все привел из небытия в бытие! В Него веровать подобает и Ему служить, а не вашим богам — бездушным идолам, бессловесным болванам!» Пам, в свою очередь, вопрошал Стефана: «Кто привел тебя в нашу землю? Кто дал тебе власть ругаться над нашими богами, разрушать их храмы и жечь огнем? Ты хочешь искоренить нашу веру, а нас одолеть и сделать подобными себе. Но берегись — отомстят наши боги за наших людей, которых ты ввел в заблуждение!»

Стефан отвечал: «Ваши боги уже погибли! Побиты они обухом, посечены топором, пожжены огнем. Ты сам видишь, что немощны они и бессильны».

Пам возражал Стефану: «Наши боги не погубили тебя лишь по своему милосердию, а могли бы сокрушить и изломать. А вера наша лучше вашей, потому что у вас только один бог, а у нас — много. И все они нам помощники, все нам защитники. Дают нам наши боги улов в наших реках и добычу в наших лесах, белок и соболей, куниц и рысей. В тех мехах, что мы добываем, величаются ваши князья и бояре, наши меха посылают и в Орду, и в Царьград, и в Литву, и в прочие города и страны, ко многим дальним народам. Потому что помогают нам наши боги, ходим мы на медведя в одиночку или вдвоем и, победив его, приносим домой медвежью шкуру. У вас же за одним медведем отправляется сотня, а то и две охотников. Иногда медведя привезут, а иногда возвращаются без добычи, напрасно потрудившись!» На эту речь Стефан отвечал: «Ты похваляешься тем, что веришь во многих богов, тогда как подобало бы этого стыдиться. Твои боги — на самом деле бесы, а идолы их — дело рук человеческих. Имеют идолы уста, а не говорят, имеют очи, а не видят, имеют уши, а не слышат. Подобны им и те, кто им поклоняется А истинный Бог един, и нет другого Бога ни на небесах, ни на земле!» Так спорили Стефан и старый волхв весь день и всю ночь без еды и без сна.

Наконец, как пишет Епифаний, «иссякли все словеса их», и они решили испытать свою веру наделе.

Испытание Стефан и Пам назначили себе такое: «Пойдем и зажжем огонь, и войдем в него вместе, взявшись за руки. Кто останется цел и невредим — того вера правильна».

А для пущей верности придумали и второе испытание: нырнуть в прорубь на Вычегде и, пройдя подо льдом, вынырнуть из другой проруби на один плес ниже. Народ, утомленный затянувшимся теоретическим спором, одобрил такое намерение: «Воистину хорошо то, что сказали вы сейчас!» Тут же принесли огня и подожгли пустующий дом, стоявший на краю селения.