Церковь в Ольты была построена по образцовому проекту военных храмов, утверждённому Строительной комиссией в 1901 г. (арх. Ф.М. Вержбицкий). Всего в Российской Империи к 1917 г. было выстроено не менее 69 таких церквей.
Церковь 1-го Горско-Моздокского полка Терского казачьего войска в честь Св. Благоверного Великого князя Александра Невского была сооружена на казенные средства и освящена 17 декабря 1909 года. Отличительной особенностью этой полковой церкви была совершенно уникальная облицовка наружных стен туфом разных тонов - тёмно-серого и песочного.
С 15.01.1892 г. и по состоянию на 1910 г. полковым священником являлся Иулиан Спиридонович Церетов.
С 1921 года, после отхода Карской губернии к Турции, церковь оказалась на территории исламского государства. По-видимому, какого-либо практического использования зданию найдено не было, однако шатёр колокольни, глава, малые луковичные главки и кресты на фасадах турками всё же были ликвидированы. Благодаря тому, что рядом с храмом пролегает оживлённая туристическая трасса, живописные полуруины храма успели стать одной из местных достопримечательностей.
В настоящее время здание бывшей церкви находится в заброшенном аварийном состоянии, являясь местом сходок местных бездомных и наркоманов, по вине которых 3 сентября 2017 г. храм серьёзно пострадал в результате пожара. Огнём были уничтожены сохранившиеся деревянные перекрытия, что привело к частичному обрушению крыши.
Источники: РГИА ф. 806, оп. 8, д. 397 (1909 г.); Цитовичъ Г.А. Храмы Армiи и Флота, 1913, с. 425-426; http://newsturk.ru/2017/09/04/v-erzurume-gorela-tserkov-aleksandra-nevskogo/