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