Церковь святителя Николая в селе Варзуга является частью некогда обширного Петропавловского Варзугского прихода, расположенного по обоим берегам одноименной реки. Сегодня это территория Терского района Мурманской области, который простирается вдоль побережья Белого моря на Кольском полуострове. В древности район также называли «Турий», что обозначало весь полуостров. Первые славянские поселения здесь появились еще в XII веке, в основном это были выходцы из новгородских и ростово-суздальских земель. В XIV-XV веках здесь уже находились владения влиятельных новгородских бояр. В 1471 году все эти земли перешли под власть великого князя московского, Ивана III Васильевича. С 1486 года обширные угодья на Терских землях принадлежали Соловецкому монастырю, а позже, Антониево-Сийскому и Спасо-Прилуцкому монастырям. До 1682 года территория входила в состав Новгородской епархии, затем Холмогорской и Важеской.

В XV-XVI веках село Варзуга считалось одним из крупнейших на «Турьем берегу». По Описи 1563 года, оно занимало обе стороны реки и имело три деревянных храма: святителя Николая и апостолов Петра и Павла на левом берегу, где находилась большая часть села, и Успения Пресвятой Богородицы на правом берегу реки Варзуги. Успенский храм, наиболее известный, существовал и ранее; первое упоминание о нем датируется 1491 годом. Это подтверждается тарханной грамотой архиепископа Новгородского Геннадия, которая освобождала Варзугскую церковь, принадлежавшую Соловецкому монастырю, от архиепископских сборов. Считается, что эта грамота относится к Успенской церкви, хотя есть мнение, что речь идет о Никольском храме с приделом Успения Пресвятой Богородицы. В 1575 году все эти храмы упоминаются как заброшенные. Причиной запустения стал опричный карательный поход 1565 года, известный как «Басаргин правеж». Лишь на рубеже XVI-XVII веков в приходе были построены еще два храма. В 1597 году, «лета 7105 мца апреля в 10 день», был возведен Афанасьевский храм, а немного позже, Зосимо-Савватиевский. В XIX веке при храмах существовали две колокольни.

Из пяти храмов до наших дней в разной степени сохранности уцелели четыре; храм во имя свв. Зосимы и Савватия Соловецких был разобран около 1877 года. Они составляют Успенский и Никольский храмовые комплексы. Из двух колоколен осталась только одна, при Успенском храме 1674 года. Остальные три храма неоднократно перестраивались. Существующий ныне храм св. Афанасия Великого, входящий в Успенский комплекс, датируется 1877 годом, а Петропавловский, 1864 годом.

Церковь святителя Николая с приделом Илии пророка впервые упоминается в 1491 году, когда ее «возобновили» на месте более древней иноки Соловецкого монастыря. В XVI веке церковь неоднократно упоминалась в писцовых книгах. Вероятно, в этот период при ней существовал придел во имя Успения Пресвятой Богородицы. Сведения о ее облике и возобновлениях до конца XVII века пока не найдены. Тем не менее, существующий ныне храм был построен заново в 1705 году на средства местных жителей и освящен 28 и 29 июня по старому стилю. Новый храм представлял собой четырехугольный сруб с крышей на четыре ската, увенчанный пятью главками, одна из которых венчала придел. В 1851 году к храму пристроили галерею с западной стороны сруба. В 1885 году на месте ветхой колокольни при храмах святителя Николая и апостолов Петра и Павла была возведена новая, но она не сохранилась до нашего времени.

Колокольный набор состоял из семи старинных колоколов XVII-XVIII веков. В 1694 году житель Каргополя пожертвовал небольшой колокол: «202 году купил сей колокол Варзугской волости церковь Петра и Павла и Николая Чудотворца на церковныя деньги каргопол Иван Андреев сын Попов, весу 25 п. 11 ф.». Еще один колокол весом в 13 пудов был отлит в 1755 году: «лит сей колокол к церкви Николая Чудотворца в Варзугу, 1755 год. Лил мастер Иван Христофоров». Наиболее интересен третий колокол весом в 125 пудов, отлитый мастерами из известной семьи литейщиков Лодыгиных: «лили сей колокол мастера Яков да Иван Лодыгины». Дата отливки неизвестна, но на основе данных о деятельности мастеров из этой семьи его можно датировать концом XVII, началом XVIII века.

В XX веке судьба храмов Варзугского прихода была печальной. Из четырех церквей в настоящее время отреставрирована только одна, Успенская. Оба храма Никольской стороны находятся в плачевном состоянии без главок, хотя в Петропавловской церкви проводятся богослужения по праздничным дням. Церковь святителя Николая до сих пор используется как магазин, в который входят через алтарь.