В 2002 году по благословению митрополита Новосибирского и Бердского Тихона было принято решение о создании прихода в честь святого страстотерпца царя Николая. Для строительства храма было выбрано место на пересечении улиц Воинской и Никитина, ранее являвшееся территорией Закаменского кладбища, ликвидированного в середине XX века. 16 апреля 2003 года на месте будущего храма был отслужен молебен перед чудотворной мироточивой иконой царя Николая.
С 2004 по 2007 год приход арендовал складское помещение по адресу улица Никитина, 107а, которое было переоборудовано под храм. В этом помещении проводились регулярные богослужения. В 2005 году на территории прихода был установлен поклонный крест в память воинов, погибших в Первой и Второй мировых войнах.
В 2006 году митрополит Тихон освятил закладной камень на месте будущего храма. В период с 2006 по 2007 год на пожертвования прихожан было построено временное здание храма. 23 марта 2007 года временная церковь была освящена. В 2009 году была сооружена звонница, содержащая шесть колоколов, отлитых на предприятии «Светолитие», и благовестник, отлитый на Московском заводе «Литекс» в 2012 году. Временная звонница представляет собой одноэтажное восьмигранное сооружение, увенчанное куполом с крестом.
В 2011 году был утверждён проект строительства постоянного храма во имя святого царя страстотерпца Николая. В 2013 году Главным управлением Министерства юстиции Российской Федерации по Новосибирской области была зарегистрирована местная православная религиозная организация «Приход храма во имя святого страстотерпца царя Николая г. Новосибирска (Октябрьский район) Новосибирской епархии Русской Православной Церкви (Московский Патриархат)».
В 2014 году митрополит Тихон освятил закладной камень на месте строительства нового храма. Строительство храма началось в том же году. 19 мая 2018 года митрополит Новосибирский и Бердский Тихон совершил чин освящения креста и купола для строящегося храма. После освящения купол был поднят и установлен на храм.
Архитектурный облик нового храма вдохновлён архитектурой собора Спасо-Андроникова монастыря в Москве. Храм выполнен в традициях древнерусского зодчества с использованием элементов, характерных для храмов XIV века. Здание представляет собой однонефную базиликальную конструкцию с вытянутым четырёхугольным планом. Над основным объёмом храма возвышается восьмерик, перекрытый куполом. Фасады украшены элементами традиционного узорочья, включая спаренные колонны, многопрофильные карнизы и арочные сандрики.
На территории храма установлен поклонный крест с надписью: «В память защитников Отечества солдат и офицеров 41 Сибирского стрелкового полка, 53 Сибирского стрелкового полка, 533 Новониколаевского пехотного полка, 476 Змеиногорского пехотного полка, 711 Нерехтского пехотного полка, 11 Сибирского стрелкового артдивизиона от благодарных потомков и земляков. 1914–1918».
