Призвав на помощь Бога и одушевленный пламенною ревностию о просвещении жителей Перми, святой Стефан с дерзновением вступил в их землю и начал возвещать им слово спасения. Одни, внимая его проповеди, веровали и крестились; другие не хотели креститься и возбраняли это веровавшим. Первые часто приходили к благовестнику, беседовали с ним и весьма его любили. От последних он терпел много поношений, озлоблении, напастей. Раз они окружили его, вооруженные, чтобы его умертвить; в другой - обложили соломою, чтобы сжечь. Но кротость его и евангельские убеждения обезоруживали ослепленных. Когда число веровавших возросло значительно, святой Стефан построил для них первую церковь во имя Благовещения Пресвятой Богородицы, имея в виду ту мысль, что как Благовещение было началом спасения для всего мира, так и церковь эта послужила начатком спасения земли Пермской. Церковь поставлена была на месте, называвшемся Усть-Вымь (при слиянии реки Вымь с Вычегдою), которое, как главное поселение зырянского народа, святой Стефан избрал главным поприщем своей апостольской деятельности. Движимый ревностию, он вскоре за тем сам сжег тайно знаменитейшую кумирницу зырян с находившимися в ней идолами и, когда неверные, подстрекаемые жрецами, устремились на него с яростию, он силою своего слова обратил многих из них ко Христу. Новосозданная церковь привлекала к себе не только уверовавших, но и неверных зырян, которые часто приходили к ней, чтобы только посмотреть на ее благолепие и полюбоваться ее красотою и отходили с мыслию о величии Бога христианского. Упорнейшие из неверных, особенно волхвы, кудесники и старцы, неоднократно собирались к Стефану и вступали с ним в торжественные прения о вере в присутствии многочисленного народа; но каждый раз были побеждаемы и посрамляемы. Вследствие этого обратилось к христианству еще великое множество мужей, жен и детей. Тогда Стефан начал учить их пермской грамоте, им изобретенной, и книгам - Часослову, Осмогласнику, Псалтири и другим, переведенным прежде, и обучившихся, судя по их успехам, одних предназначал во священники, других - в диаконы, третьих - в чтецы. Учил их также церковному пению и письму, заставляя их переписывать книги, а сам переводил другие с русского языка на пермский. Радуясь успеху предприятия и видя, как ежедневно умножалось стадо Христово, святой благовестник построил еще церковь в Усть-Выме, а равно и другие церкви в разных местах по рекам и по погостам, где жили зыряне. Сооружение церквей сопровождалось повсюду сокрушением идолов. Святой Стефан сам с учениками своими днем и ночью, при народе и без народа обходил леса, погосты, распутия, входил в домы жителей и, где только ни отыскивал кумиры и кумирницы, все это разрушал и предавал огню. Равным образом все приношения язычников, которые были повешены вокруг идолов или над ними и служили к украшению их, как-то: шкуры соболей, куниц, горностаев, бобров, лисиц, белок и других зверей, - собирал в кучи и сжигал к немалому изумлению зырян, которые не могли понять, почему он не хотел воспользоваться сам всеми этими драгоценностями 181.
Оставался у Стефана еще один враг, самый сильный и опасный. Это был глубокий старец, знаменитейший кудесник и начальник волхвов, которого зыряне издавна чтили более всех своих чародеев и называли своим наставником и учителем. Имя ему было Пам или Пансотник. Своим сильным влиянием он неверных зырян удерживал в неверии, а новокрещеных совращал и привлекал к себе то своим льстивым учением, то мнимыми чародеяниями, то обещаниями и дарами. "Не оставляйте, - говорил он между прочим, - отеческих богов, не слушайте Стефана, пришедшего из Москвы. Может ли быть для нас из Москвы что-либо доброе? Не оттуда ли пришли на нас тяжкие дани, и насильства, и тиуны, и приставники? Но меня слушайте, вашего единоземца, единоплеменника и давнего учителя, желающего вам добра, меня, старца, а не того русина-москвитянина, который по летм годился бы мне в сыны и даже внуки..." Много раз святой Стефан вступал в открытые прения с злым кудесником, и эти прения длились иногда целые дни и ночи, но кудесник оставался непреклонен. Наконец, оба они согласились испытать достоинство вер, христианской и зырянской, посредством огня и воды и именно положили, что оба они вместе, рука в руку, пройдут сквозь пылающий костер и потом спустятся в одну прорубь реки Вычегды, чтобы чрез несколько времени выйти в другую, и кто останется цел и невредим, того вера признана будет истинною. Стефан приказал собравшемуся народу зажечь одну храмину, стоявшую особо, и, когда пламя охватило ее, он, призвав на помощь Бога и обращаясь к волхву, начал приглашать его идти в огонь вместе. Но устрашенный волхв не соглашался. Стефан взял его за одежду и нудил идти за собою, волхв сопротивлялся и в крайнем уничижении пал к стопам человека Божия, сознавая свою немощь. Все присутствовавшие еще три раза призывали его идти в горевшее пламя, и он трикраты отрекся. Точно так же отрекся он и спуститься вместе с Стефаном в прорубь реки Вычегды, сколько его к тому ни приглашали, а в оправдание себя говорил народу: "Я не ожидал, что Стефан в самом деле решится идти в огнь и в воду; но он, верно, еще в детстве научился от своего отца заговаривать огнь и воду посредством какого-либо волшебства, которое мне неизвестно". Никто, однако ж, уже не верил посрамленному кудеснику. Его схватили и хотели умертвить. Святой Стефан не допустил этого, а приказал только, чтобы кудесник удалился из пределов пермских и более не совращал новообращенных христиан, на что и сам кудесник согласился, обещаясь в противном случае признать себя достойным смерти, и действительно, как гласит предание, переселился с своими сообщниками на реку Обь в пределы нынешней Тобольской губернии 182.
Последовали новые и новые обращения зырян, которые приходили со всех сторон к проповеднику Евангелия, и он, по обычаю, оглашал их и крестил. А между тем сам продолжал заниматься переводами с славянского и греческого языков на пермский и иногда даже ночи проводил над перепискою книг. Книги нужны были для новых церквей, которые, с умножением числа верующих, устроял он на разных местах, по рекам и погостам. А так как для церквей необходимы были и священнослужители и каждый раз посылать избранных в другие епархии для поставления на священные степени было крайне неудобно, то святой Стефан пришел к мысли испросить пермянам постоянного епископа, и с этою целию, после четырехлетних апостольских трудов своих между ними, отправился в Москву 183. Митрополит Пимен, одобрив эту мысль, после совещания с епископами, из которых одни указывали на того, другие - на иного кандидата, остановился сам на святом Стефане как достойнейшем из всех для занятия епископской кафедры в Перми, так как он был муж мудрый, благочестивый, учительный, сам крестил пермян, говорил их языком и лучше других понимал их нужды. Великий князь с радостию согласился на такое избрание, потому что весьма хорошо знал Стефана и издавна любил его. И Стефан рукоположен был во епископа зимою 1383 г., в одно время с Смоленским епископом Михаилом 184. Одаренный от князя, митрополита, бояр и других христоименитых людей, новопоставленный епископ Пермский с радостию прибыл в свою епархию, утвердил свою кафедру в Усть-Выме, где жил и прежде при церкви Благовещения, устроив здесь свой домовый Архангельский монастырь, и еще с большею ревностию принялся за свое прежнее дело. "Он, - скажем словами его жизнеописателя, - повсюду изыскивал, где оставались некрещеные, и, в каких бы пределах ни находил их, обращал от язычества и крестил; а всех крещеных утверждал в вере и убеждал простираться вперед. Учил их пермской грамоте, писал им книги, ставил и святил церкви, которые снабжал книгами и иконами, открывал монастыри, постригал в чернецы, устроял игуменов, поставлял священников, диаконов и причетников. И священники его служили обедни на пермском языке, пели вечерню и заутреню пермскою речью; и канонархи его возглашали каноны по пермским книгам, и чтецы читали пермскою беседою, и певцы всякое пение совершали по-пермски". Из основанных святым Стефаном обителей известны две: Спасо-Ульяновская, находившаяся в 150 верстах от Усть-Сысольска, и Стефановская - в 50 верстах от этого города на реке Сысоле, в нынешнем селе Вотче 185. Однажды святой Стефан, желая испытать обращенных им к святой вере, сказал им: "Покажите мне свою веру от дел. Разведайте и разыщите, не скрываются ли где кумиры: в ваших ли домах, или у соседей, или в других потаенных местах, - и пусть каждый истребит найденные им кумиры всенародно". Тогда все крещеные зыряне, наперерыв друг перед другом и опасаясь друг друга, старались открывать и истреблять кумиры и таким образом окончательно очистили от них свои жилища 186.