Место для возведения солдатской церкви Барнаульского стрелкового полка в начале ХХ века было выделено на центральном городском проспекте, недалеко от полковых казарм. Строительство заняло меньше двух лет, и с 1906 года все призывавшиеся на военную службу из Барнаула принимали в этом храме присягу. На прилегающей к церкви территории проводились масштабные празднования.

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