Храм был заложен в 1904 году на Московском проспекте. Уже в 1906 году строительство было закончено, а храм освящён.

Никольский храм построен по типовому проекту для военных храмов (архитектор — Фёдор Михайлович Вержбицкий), утверждённому Строительной комиссией в 1901 году. Всего к 1917 году в Российской Империи по этому проекту было выстроено не менее 60-ти таких храмов. Постройка воинского храма в Барнауле велась под наблюдением местного архитектораИ. Ф. Носовича. Здание выдержано в стиле эклектики с элементами русско-византийского стиля. Принадлежит к типу однонефных базиликальных храмов. Монументальное здание из красного кирпича с трёхъярусной колокольней и торжественным порталом на западном фасаде вписывается в окружающий архитектурный ансамбль. Храм был рассчитан на 400—600 человек.

Храм находился рядом с казармами Барнаульского полка и носила статус «полковой». Здесь военнослужащие принимали присягу. У стен храма в 1912 году проходили торжества по случаю победы России в Отечественной войне 1812 года и 300-летие Дома Романовых.

В 1930-х годах храм был закрыт. С него сняли купол и разрушили колокольню. Долгое время здание использовалось под клуб военной части, а позднее Барнаульского высшего военного училища лётчиков.

В 1991 году во время визита Алексия II на Алтай здание было передано Русской православной церкви. В 1990—2000-х годах храм был реконструирован и в нём возобновились богослужения. Барнаульский художник В. Коньков завершил его внутреннюю роспись, готов новый иконостас, написанный палехскими мастерами-иконописцами, действует новая колокольня.

В июне 2006 года была закончена реконструкция первого купола, значительно преобразившего внешний вид храма. А 21 мая 2007 года на нём были установлены пять золочённых крестов: один из которых расположен в центре над входом, и по два — с каждой из его сторон.