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