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