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

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

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

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

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

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

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

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

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

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

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

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

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

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

Со временем христианство распространилось почти по всей Пермской земле, и возникла необходимость в создании церковной организации.

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

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

Стефан вернулся в Пермскую землю, «радуяся, благодаря Бога, устроившего все добре зело».

Долгие годы прожил Стефан среди пермян, пользуясь их любовью и уважением, был им не только наставником, но и заступником. Когда жители Вятки совершили грабительский набегна пермян, Стефан организовал отпор. Во время голода он хлопотал о доставке хлеба из Вологды. Ездил в Новгород увещевать новгородских старейшин, чтобы они не разрешали своим ушкуйникам бесчинствовать на Пермской земле.

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

Единственный рассказ о чуде, связанном с именем Стефана, содержится не в его житии, а в житии Сергия Радонежского.

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