Первые русские церковные приходы появляются в Армении в начале XIX века. В 1801 году указом императора Павла I к Российской империи было присоединено Картли-Кахетинское царство (Восточная Грузия), в составе которого тогда была территория Лоре-Ташири (историческая Северо-Западная Армения).

На присоединенных землях стали расквартировываться казачьи войска. Казаки сооружали в населенных пунктах православные часовни и церкви, где принимали военную присягу. В 1811 году с учреждением Грузинского Экзархата РПЦ территории Лоре-Ташири в церковном отношении вошли в юрисдикцию Мцхетско-Карталинской епархии Экзархата.

1 октября 1827 года, в день Покрова Пресвятой Богородицы, русскими войсками была взята Эриванская крепость. Старая эриванская греческая церковь, в свое время превращенная персами в мечеть, была вновь освящена как православная в честь Покрова Пресвятой Богородицы и почиталась как памятник взятия Эривани. В 1830 году также в память о взятии Эриванской крепости в городе в псевдорусском архитектурном стиле был воздвигнут храм в честь Покрова Пресвятой Богородицы, который жители города назвали «Русская церковь».

В 1828 году по условиям Туркманчайского мира с Персией частью Российской империи стало Эриванское ханство. Эривань стала столицей Армянской области, с 1849 года именуемой Эриванской губернией.

Основу православного населения Армении составили русские военные поселенцы и отставники, администраторы, члены их семей, позже — крестьяне из внутренних областей империи.

Недалеко от Степанавана, в селе Амракиц (Лорийская область Армении) сохранилась церковь святого Николая Чудотворца. Раньше это село называлось Николаевка: оно было основано украинскими казаками.

В 1846 году для православных верующих казачьей станицы Николаевка основали небольшую церковь, освященную во имя святого Николая Чудотворца. Дошедшее до наших дней здание построено, по всей видимости, в 10-х годах ХХ века. Небольшое сооружение представляет собой замечательный образец неорусского направления архитектуры модерна, близкий к проектам архитектора и художника Андрея Петровича Аплаксина. Рукава слегка вытянутого в длину крестообразного объема храма имеют клинчатые кровли, завершающиеся главками. Над средокрестием возвышается надстройка с пирамидальным завершением, увенчанным миниатюрным пятиглавием. Колокольня, размещенная по диагонали относительно храма, построена в виде объемной открытой звонницы и увенчана крестообразной клинчатой кровлей. Приход был в ведении Грузинской православной церкви.

Здание церкви святого Николая Чудотворца сильно пострадало во время Спитакского землетрясения 1988 года. Сегодня церковь не действует, богослужения в ней не ведутся. Здание находится в аварийном состоянии и нуждается в реставрации.

В 2009 году иконы и священнические облачения были переданы из церкви святого Николая Чудотворца в храм святой мученицы Царицы Александры и часовне святого Архистратига Михаила в Гюмри.