La iglesia del santo Nicolás en el pueblo de Varzuga es parte de la alguna vez extensa parroquia de Petropavlovsk Varzugski, ubicada a ambos lados del río homónimo. Hoy en día, es territorio del distrito de Tersky en la región de Murmansk, que se extiende a lo largo de la costa del mar Blanco en la península de Kola. En la antigüedad, la región también se conocía como "Turiy", que designaba toda la península. Los primeros asentamientos eslavos aquí aparecieron ya en el siglo XII, principalmente eran emigrantes de las tierras de Novgorod y Rostov-Suzdal. En los siglos XIV-XV, ya había propiedades de influyentes boyardos novgorodenses. En 1471, todas estas tierras pasaron bajo el dominio del gran príncipe de Moscú, Iván III Vasílievich. Desde 1486, vastas tierras en las tierras de Tersky pertenecieron al monasterio de Solovetsky, y más tarde, a los monasterios de Antoniev-Siy y Spaso-Prilutsky. Hasta 1682, el territorio formaba parte de la diócesis de Novgorod, luego de la de Kholmogory y Vazhsky.

En los siglos XV-XVI, el pueblo de Varzuga se consideraba uno de los más grandes en la "orilla Turiy". Según el inventario de 1563, ocupaba ambos lados del río y tenía tres templos de madera: el de San Nicolás y los apóstoles Pedro y Pablo en la orilla izquierda, donde se encontraba la mayor parte del pueblo, y el de la Asunción de la Santísima Virgen en la orilla derecha del río Varzuga. El templo de la Asunción, el más conocido, existía antes; la primera mención de él data de 1491. Esto se confirma con el decreto del arzobispo de Novgorod, Genadio, que eximía a la iglesia de Varzuga, perteneciente al monasterio de Solovetsky, de los tributos arzobispales. Se considera que este decreto se refiere a la iglesia de la Asunción, aunque hay opiniones de que se trata del templo de Nicolás con la capilla de la Asunción de la Santísima Virgen. En 1575, todos estos templos se mencionan como abandonados. La razón del abandono fue la campaña punitiva de 1565, conocida como "la represión de Basargin". Solo a finales de los siglos XVI-XVII se construyeron dos templos más en la parroquia. En 1597, "en el año 7105, en el mes de abril, el día 10", se erigió el templo de Afanásievsky, y poco después, el de Zosimo-Savvatiyevsky. En el siglo XIX, había dos campanarios junto a los templos.

De los cinco templos, hasta nuestros días han sobrevivido cuatro en diferentes grados de conservación; el templo en honor de los santos Zosima y Savvaty de Solovetsky fue desmantelado alrededor de 1877. Ellos constituyen los complejos de los templos de la Asunción y de Nicolás. De los dos campanarios, solo queda uno, junto al templo de la Asunción de 1674. Los otros tres templos han sido reconstruidos en varias ocasiones. El templo actual de San Afanásio el Grande, que forma parte del complejo de la Asunción, data de 1877, y el de Petropavlovsky, de 1864.

La iglesia del santo Nicolás con la capilla del profeta Elías se menciona por primera vez en 1491, cuando fue "renovada" en el lugar de un más antiguo de los monjes del monasterio de Solovetsky. En el siglo XVI, la iglesia se mencionó repetidamente en los libros de registro. Probablemente, en este período existió una capilla en honor a la Asunción de la Santísima Virgen. No se han encontrado datos sobre su apariencia y renovaciones hasta finales del siglo XVII. Sin embargo, la iglesia actual fue construida de nuevo en 1705 con fondos de los habitantes locales y fue consagrada el 28 y 29 de junio según el antiguo calendario. La nueva iglesia era un edificio cuadrado con un techo a cuatro aguas, coronado con cinco cúpulas, una de las cuales coronaba la capilla. En 1851, se añadió una galería al templo desde el lado oeste del edificio. En 1885, en el lugar del antiguo campanario de las iglesias de San Nicolás y de los apóstoles Pedro y Pablo, se erigió uno nuevo, pero no ha sobrevivido hasta nuestros días.

El conjunto de campanas consistía en siete antiguas campanas de los siglos XVII-XVIII. En 1694, un habitante de Kargopol donó una pequeña campana: "En el año 202, compró esta campana para la iglesia de Pedro y Pablo y de Nicolás el Milagroso en la parroquia de Varzuga con dinero de la iglesia, Iván Andreyev hijo Popov de Kargopol, peso 25 p. 11 f.". Otra campana de 13 púd fue fundida en 1755: "se fundió esta campana para la iglesia de Nicolás el Milagroso en Varzuga, año 1755. Fundió el maestro Iván Christoforov". La tercera campana, de 125 púd, fue fundida por maestros de la conocida familia de fundidores Lodygin: "fundieron esta campana los maestros Yákov e Iván Lodygin". La fecha de fundición es desconocida, pero basándose en datos sobre la actividad de los maestros de esta familia, se puede datar a finales del siglo XVII, principios del XVIII.

En el siglo XX, el destino de las iglesias de la parroquia de Varzuga fue triste. De las cuatro iglesias, actualmente solo se ha restaurado una, la de la Asunción. Ambas iglesias del lado de Nicolás se encuentran en un estado lamentable sin cúpulas, aunque en la iglesia de Petropavlovsky se celebran servicios en días festivos. La iglesia del santo Nicolás se utiliza hasta hoy como tienda, a la que se accede a través del altar.