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