В 1379 г. в Вычегодскую Пермь, с 1328 г. платившую подати московским князьям, из Москвы прибыл иеромонах Стефан. В продолжение нескольких лет, двигаясь по берегам рек Вымь и Вычегда, он проповедовал христианство зырянам. При слиянии этих рек построил церковь в честь Благовещения Пресвятой Богородицы, клир которой составили новообращённые жители Вычегодской Перми. Позднее вокруг храма вырос погост Усть-Вымь. В 1383 г. Стефан в Москве был хиротонисан во епископа для новоучреждённой Пермской епархии. Стефан крестил около 700 человек, избрал из их числа способных и рукоположил во священный сан, поставил также иподиаконов, чтецов. Святитель создал коми-зырянский алфавит и перевёл на коми-зырянский язык Часослов, Псалтирь, Октоих и другие богослужебные книги. Построил в Перми храм во имя архангела Михаила, при котором в XVI в. возник усть-вымский во имя архангела Михаила мужской монастырь, основал Спасо-Ульяновский Стефанов во имя Святой Троицы и Стефанов во имя Афанасия Великого на Вотче мужской монастыри. Не желавшие принимать христианство зыряне и коми-пермяки во главе с сотником Паном переселились с Вычегды на берега Оби. В 1385 г. Новгородский архиепископ Алексий послал дружинников, чтобы изгнать Стефана из Перми. Нападение удалось отразить с военной помощью из Устюга. В следующем году Стефан ездил в Великий Новгород, конфликт с архиепископом был урегулирован, Пермский архиерей оказал поддержку архиепископу Алексию в борьбе с ересью стриголников. Святителю удалось уменьшить размер дани, которую платили пермяки данщикам, наместникам и в великокняжескую казну. Во время голода в крае епископ Стефан организовал доставку хлеба в Пермь из Вологды. Попытки язычников ограбить и уничтожить Усть-Вымь и Еренский городок (например, в 1390 г.) пресекались посылкой в Пермь военной помощи из Устюга. В 1396 г. Стефан направился в Москву, где скончался 26 апреля. Расширение пределов Пермской епархии приходится на время деятельности епископов Питирима (1444–1456 гг.) и Ионы (1459–1470 гг.), просветивших крещением Великую Пермь. В 1451 г. Пермский князь Михаил Ермолаевич принял крещение в Москве и вернулся в Великую Пермь в качестве великокняжеского наместника. В 1455 г. в Великую Пермь приезжал епископ Питирим «крестити ко святей вере чердынцев», на обратном пути, уже в вычегодских землях, он был замучен хантами (вогулами). В 1462 г. епископ Иона «добавне крести Великую Пермь, постави им церкви и попы и княжат Михайловых (детей Михаила Ермолаевича) крести». Чрезвычайно сложным было служение Питирима, совпавшее по времени с борьбой за Московское великое княжество между Василием II Васильевичем и Дмитрием Шемякой. Шемяка пользовался поддержкой жителей соседней Вятки, в 1450 г. разоривших земли Пермской епархии. В 1452 г. Питирим был в плену у Шемяки, который подверг епископа мучениям за отказ снять с него церковное отлучение. В 1480–1481 гг. против великого князя Ивана III Васильевича выступила языческая знать хантов и манси во главе с князем Асыкой, а также правители югорских княжеств. Языческие правители не стремились к уничтожению христианства в Перми, в качестве посредника при их переговорах с великим князем выступил епископ Филофей (1471–1501 гг.).