Приход Каркси-Нуйя в Вильяндиском уезду был основан в 1847-ом году. Изначально богослужения проходили в здании мызы Каркси, а в 1852-ом году приход перебрался в армейский квартирный дом при мызе Каркси. Собственной каменной церковью приход обзавёлся в 1868-ом году. Церковь построена по проекту архитекторо А. Эдельсона. С западной стороны церкви располвгается колокольня. Башня с округлыми сводами и круглыми оконными проёмами покрыта жестяной крышей. Небольшая башня, увенчанная шатром, располагается над алтарной частью главного придела. Церковь была освящена в честь святителя Алексия Московского только после приёма здания в 1876-ом году. Первым священником прихода Каркси-Нуйя в период с 1847-го по 1849-ый годы являлся К. Сарнет. В 1890-ом году число прихожан составляло 3197-человек, а в 1938-ом - 2229 человек. В период с 1903-го по 1908-ой годы в приходе служил Александр Павла, будущий митрополит Эстонской Апостольской Православной Церкви. С 1952-го года и вплоть до своей смерти в 1992-ом году в приходе служил протоирей В. Линд, который в период советской власти остался единственным православным священником в Вильяндиском уезде.