За время пребывания в монастыре Стефан окончательно утвердился в мысли, к которой, по-видимому, пришел еще в родном городе: просветить язычников-зырян, приобщить их к христианской вере. Но для этого необходимы священные книги, понятные для невежественных язычников. «И обучился Стефан сам языку пермскому, и грамоту новую пермскую сложил, и азбуку ранее неизвестную пермского языка сочинил, как полагается, и книги русские на пермский язык перевел, и переложил, и переписал». Это был великий подвиг, подобный совершенному некогда святыми Кириллом и Мефодием, просветителями славян. Как полагают, изобретая азбуку для языка коми-зырян, Стефан использовал значки, вырезавшиеся зырянами на тонких четырехугольных палочках, которые служили им в качестве денег. Новоизобретенными знаками были переписаны основные богослужебные книги — по всей видимости, Часослов, Псалтирь и Служебник.
К тому времени, уже несколько лет пребывая в монастыре, Стефан был рукоположен в диакона. В 1379 году, перед началом своей проповеди, Стефан отправился за благословением к местоблюстителю митрополичьего престола коломенскому епископу Герасиму. Епископ весьма удивился его замыслу, но, видя его искреннее желание и готовность к подвигу, благословил Стефана. Тогда же он возвел его в сан священника и снабдил всем необходимым для освящения церкви. Стефан получил разрешение на свою деятельность и от гражданских властей и запасся охранной грамотой великого князя Дмитрия Ивановича. Однако никто из представителей властей не последовал за ним. Стефан отправился в Пермскую землю один. Более того, впоследствии ему не раз придется защищать пермяков от насилия княжеских тиунов и приставов.
Святой начал свою проповедь с Котласа (Пырас). Поначалу ему пришлось претерпеть много зла от язычников, рассказывает Епифаний: «озлобление, ропот, поругание, хулу, укоры, уничижение, досаждения, поношение, пакости, а иногда и угрозы: смертью угрожали ему, даже убить хотели, обступали его с дубинами и с длинными жердями, нанести смертельные удары хотя. Однажды собралось против него множество крамольников, и, принесши множество охапок сухой соломы и огонь, обложили они его кругом той соломой и хотели по воле своей сжечь». Однако Господь защитил его. Святой противопоставлял злу кротость и смирение; он сам не поднимал руки против язычников и сносил их брань и угрозы, но при том неустанно продолжал свою проповедь.
Вскоре, окрестив нескольких местных жителей, святой Стефан поставил церковь в устье реки Выми (притока Вычегды). Впоследствии он устроил в Усть-Выми монастырь, ставший главным центром новой епархии.
Житие рассказывает о таком случае. Однажды святой Стефан пришел к особо почитаемому святилищу пермяков, где стояли их идолы, сделанные из дерева. В это время там никого не было. Стефану удалось поджечь идолов, и святилище сгорело дотла. Святой не бежал прочь, но остался на том месте, ожидая язычников. Те, действительно, вскоре прибежали, объятые яростью, и устремились на него с топорами и дрекольем, помышляя убить. Стефан не стал ничего говорить им, но обратился с молитвой к Богу — и внезапно ярость народа, окружавшего его, сменилась успокоением. Никто даже не ударил его — отчасти потому, что кротость святого смирила их, отчасти, наверное, потому, что люди побоялись тронуть человека, пришедшего с грамотами из самой Москвы. И позднее они нередко рассуждали так: «Как можем мы бить или прогонять его, когда он имеет грамоты из Москвы? Вот если бы он первым вступил в борьбу и ударил кого-нибудь из нас, то мы бы растерзали его и тем могли оправдаться. Но он в ответ на наши обиды не скажет гневного и укорительного слова, все перенося с терпением, и мы не знаем, что нам делать с ним».
Как только святой Стефан замечал где-либо собравшихся язычников, он тут же спешил к ним и вступал в беседу, проповедуя о Христе. Иногда люди сами приходили к нему для беседы. Особенно часто являлись они в церковь, построенную святым, — даже не из-за молитвы, но из желания посмотреть на невиданную ими прежде красоту храма. (Так когда-то и сами русские уверовали в Христа, пленившись красотой церковной службы.) И так все большее число людей приобщалось к христианской вере.
Святой прошел не менее тысячи километров по земле Перми. Он разрушал святилища и срубал священные деревья зырян — все чаще уже при помощи самих вчерашних язычников, принимавших крещение. Старые божества не могли покарать его — и это в глазах народа служило доказательством истинности учения, принесенного святым Стефаном. У местных жителей был обычай украшать идолы лучшими шкурами пойманных на охоте зверей — соболей, куниц, горностаев, а также другими драгоценностями. Никто не смел прикасаться к ним — ослушника неминуемо поражала лютая болезнь. Святой же безбоязненно срывал драгоценности, принесенные, как он говорил, в дар бесам, и бросал все их в огонь. (Впрочем, одному из своих слуг он повелел сделать из драгоценных шкур штаны, онучи и «ноговицы» и носить их на посмеяние бесам.) Себе же святой ничего не брал — и это его бескорыстие также вызывало изумление пермяков, привыкших к жадности выходцев из Москвы.
Житие рассказывает о споре святого с неким волхвом-чародеем по имени Пам. Прежде тот считался первым во всей Пермской земле, проповедь же святого лишила его власти и богатства. Пам не раз подговаривал местных жителей прогнать Стефана из страны и возвратиться к вере отцов и дедов. «Что доброго может быть нам от Москвы? — говорил он. — Не оттуда ли нам идут тяготы, дани тяжкие и насилия, и тиуны, и доводчики, и приставники? Того ради не слушайте его, но меня лучше слушайте». Люди же отвечали, что Паму надлежит спорить не с ними, но с самим Стефаном: если он одолеет того, то и они оставят новое учение и вернутся к старым богам.
Стефан и Пам в течение целого дня препирались друг с другом, причем Стефан, согласно рассказу Жития, опроверг все доводы волхва о преимуществах его веры. Наконец, потеряв надежду одолеть христианского проповедника в словесном поединке, волхв предложил делом испытать, на чьей стороне истина, а именно пройти испытания огнем и водою: и Стефан, и сам волхв должны были войти в пламя — тот, кто выйдет целым и невредимым, докажет истинность своего учения. Затем оба должны были войти в одну прорубь на реке Вычегде (дело было зимой) и выйти из другой. Стефан согласился. Подожгли некую хижину, и, когда та запылала, святой, помолившись, взял за руку волхва и решительно направился в самое пламя. Но, оказывается, волхв был храбр только на словах: он испугался сильного пламени и не посмел войти в него. Святой схватил его за одежду и стал силой волочь в горящую хижину. Пам упирался, пятился назад и, наконец, упав на землю, стал вопить, что боится прикоснуться к огню. И так повторялось трижды. Преподобный, одержав победу над волхвом, обратился к народу, спрашивая, как надлежит поступить с осрамившимся кудесником. «Достоин он казни», — отвечали люди. Волхва схватили и подвели к Стефану. Стефан, однако, отказался казнить его, но изгнал его из страны. Об этом Паме известно, что он со своим родом ушел в Сибирь; согласно преданию, жители селения Алтым на Оби вели от него свое происхождение.
Число учеников Стефана непрестанно увеличивалось. Строились новые церкви, так что возникла нужда в особом епископе для Пермской земли. Около 1383 года Стефан отправился в Москву к великому князю Дмитрию Ивановичу и митрополиту Пимену, управлявшему тогда Русской Церковью, просить их о поставлении епископа для новообращенных людей. Митрополит Пимен рукоположил в епископа Пермского самого Стефана. При этом великий князь пожаловал Стефану часть своих доходов с Перми, право беспошлинной торговли в русских землях и сбор пошлин с приезжавших в Пермь купцов и промышленников. Новый епископ получил и богатые дары от великого князя.
В сане епископа святой Стефан трудился для пермской Церкви столь же усердно, как и раньше: он приводил к вере и крестил язычников, ставил церкви, поставлял священников, устраивал монастыри. Известны основанные им монастыри: два Архангельских — в Усть-Выми и Яренске, Спасский и Стефановский в районе Усть-Сысольска. Великой заслугой святого было распространение школ, в которых Стефан обучал своих учеников изобретенной им грамоте; он организовывал переписку книг, продолжил перевод на пермский язык богослужебных книг — причем не только со славянского, но и с греческого языка. (К сожалению, ни одной книги, написанной пермским языком, до нашего времени не сохранилось; уцелели лишь отдельные надписи.) Стефан стал великим благодетелем для всего пермского народа. Он заботился не только о духовных нуждах своей паствы, но и о ее материальном благополучии. Во время голода, охватившего пермские земли, святитель раздавал голодающим свои хлебные запасы и деньги, заботился о доставке хлеба из Устюга и Вологды. Он старался обезопасить Пермь от нападения ее беспокойных соседей — вогуличей (нынешние манси), вятчан, а также новгородских разбойников-ушкуйников. В 1386 году Стефан с этой целью посетил Новгород. Он бывал и в Москве. В 1391 году Стефан участвовал в соборе епископов, созванном митрополитом Киприаном. Вероятно, именно во время этой его поездки в Москву произошло известное чудо, свидетельствующее об особой духовной близости, установившейся между святым Стефаном Пермским и святым Сергием Радонежским. О чуде этом рассказывается в Житии Сергия.
