Церковь была заложена в 1904 году на Московском проспекте. Уже в 1906 году строительство было закончено, а храм освящён.
Никольская церковь построена по типовому проекту для военных церквей (архитектор- Фёдор Михайлович Вержбицкий), утверждённому Строительной комиссией в 1901 г. Всего к 1917 г. в Российской Империи по этому проекту было выстроено не менее 60- ти таких церквей. Постройка воинского храма в Барнауле велась под наблюдением местного архитектора И. Ф. Носовича. Здание выдержано в стиле эклектики с элементами русско-византийского стиля. Принадлежит к типу однонефных базиликальных храмов. Монументальное здание из красного кирпича с трёхъярусной колокольней и торжественным порталом на западном фасаде вписывается в окружающий архитектурный ансамбль. Храм был рассчитан на 400-600 человек
Церковь находилась рядом с казармами Барнаульского полка и носила статус «полковой». Здесь военнослужащие принимали присягу. У стен храма в 1912 году проходили торжества по случаю победы России в Отечественной войне 1812 года и 300-летие Дома Романовых.
В 1930-х годах церковь была закрыта. С неё сняли купол и разрушили колокольню. Долгое время здание использовалось под клуб военной части, а позднее Барнаульского высшего военного училища лётчиков.
В 1991 году во время визита Алексия II на Алтай здание было передано общине верующих города. В 1990-2000-х годах церковь была реконструирована и в ней возобновились службы. Барнаульский художник В. Коньков завершил его внутреннюю роспись, готов новый иконостас, написанный палехскими мастерами-иконописцами, действует новая колокольня.
В июне 2006 года была закончена реконструкция первого купола, значительно преобразившего внешний вид храма. А 21 мая 2007 года на нём были установлены пять золочённых крестов: один из которых расположен в центре над входом, и по два - с каждой из его сторон.