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