Первая деревянная Никольская церковь в селе Воя была освящена в 1729 году. После пожара 7 декабря 1741 года, уничтожившего первоначальный храм, 23 марта 1742 года Казанская духовная консистория издала указ о строительстве новой деревянной церкви во имя Святого Николая Чудотворца. Строительство завершилось в 1743 году, и 31 декабря того же года церковь была освящена. Однако 14 марта 1787 года и эта церковь сгорела. 25 мая 1787 года была выдана храмозданная грамота на строительство очередной деревянной церкви с приделом в честь Святого Василия Великого. Новый храм был построен и освящен 1 и 2 января 1788 года.
В 1816 году, ввиду ветхости деревянного строения, было принято решение о возведении каменного храма. 9 сентября 1816 года была выдана соответствующая храмозданная грамота. Строительство каменной церкви продолжалось до 1821 года. Новый храм имел два престола: в холодной части — во имя Святителя Николая Чудотворца, в теплой — в честь Святого Василия Великого.
К началу XX века приход Никольской церкви включал 28 селений с общим числом прихожан: 1 136 мужчин и 1 218 женщин православного русского населения, а также 863 мужчины и 887 женщин крещеных черемисов. Штат причта состоял из священника и псаломщика, для которых были предусмотрены казенные квартиры. Земельные владения церкви включали 4 десятины усадебной земли, 35 десятин пахотной, 5 десятин сенокосной и 4 десятины неудобной земли. Братский денежный доход составлял: священнику — 623 рубля 4 копейки, диакону — 415 рублей 36 копеек, псаломщику — 207 рублей 68 копеек. Дополнительно на весь причт собиралось до 15 пудов ржи и 50 пудов овса.
Село Воя расположено в низменности при речке Войке, в безлесной местности. В приходе функционировали образовательные учреждения: церковно-приходская школа в селе, миссионерская школа грамоты в 4 верстах и два одноклассных министерских училища в 7 и 9 верстах. Основным занятием прихожан было хлебопашество.
