Основание прихода можно отнести ко второй половине XVII века. В Кудымкорской церкви, как редкость, хранится расколотый колокол, на котором следующая надпись: «Anno 1647 Gloria Soli Deo». В 1715 году, по свидетельству очевидцев Воронцова, Вельяминова и Синявина, составлявших переписные книги князя Гагарина, было село Кудымкорское у речки Кувы, а в нем церковь деревянная во имя Николая чудотворца». Штат составляли: священник, дьячок, пономарь и просвирня. Церковь эта существовала до начала XIX века. Она разобрана в 1805 году, по резолюции Преосвященного Иустина Епископа Пермского, и часть леса и внутренних построек пошли «на благопристойныя поделки» во вновь построенной церкви. Старожилы уверяют, что эта деревянная церковь была уже не первая в Кудымкоре. Они, по преданию, указывают и место, где существовала первая, доисторическая церковь. Настоящая, каменная, трехпрестольная церковь заложена в 1796 году. В этом году поверенный Пермских вотчин и соляных промыслов и заводов графа Александра Сергеевича Строганова, Яков Бушуев, просил Преосвященного Лаврентия Епископа Вятского и Великопермского разрешить построение в селе Кудымкоре каменной церкви вместо деревянной и в прошении говорил, «что в селе Кудымкорском деревянная церковь, сознанная во имя святителя Николая чудотворца, от долговременного стояния весьма обветшала и к священнодействию впредь прочности не предвидится». Первоначально она была двухпрестольная: во имя святителя Николая и мученицы Параскевы. Впоследствии (в 1812 г.) появился и третий придел во имя сорока мучеников Севастийских. Об освящении первых двух престолов свидетельствуют надписи, сохранившиеся в алтарях. В храме есть икона святителя Николая очень древнего письма. Образ перенесен сюда из последней деревянной церкви.
