15 мая 1897 года состоялась торжественная закладка каменного храма во имя святого благоверного князя Александра Невского, святого покровителя императора Александра Третьего.
На торжественный молебен по случаю закладки храма приехал даже томский губернатор, генерал-майор Асинкрит Асинкритович Ломачевский. Присутствовал также начальник Среднесибирского участка Транссиба Николай Павлович Меженинов, инженеры-путейцы и большое количество народу.
В «Путеводителе по Великой Сибирской дороге», изданном в 1901 году, приводится вот такое описание посёлка Ново-Николаевского:
«В центре поселения, раскинувшегося почти на 10 верст вдоль берегов реки Оби и ее притока реки Каменки, сооружен на суммы, пожертвованные Его Императорским Величеством и на жертвы и приношения частных лиц красивый каменный храм, долженствующий служить памятником Царю-миротворцу на Великом Сибирском пути…»
История строительства Храма Александра Невского началась 10 октября 1895 года. Тогда группа жителей поселка в устье Каменки числом 21 человек, — это строители моста, купцы, мещане и чиновники, — решила ходатайствовать перед томским епископом Макарием о том, чтобы закрыть «кабаки и притоны, взамен построить церковь во имя Александра Невского», а пока возвести временный молитвенный дом. Деревянный молитвенный дом с отдельной колокольней действительно построили, и всего за месяц.
Для сбора пожертвований на строительство каменного храма организовали комитет, который возглавил Николай Меженинов. Строительство же по приказу Министерства путей сообщения возглавил инженер-путеец Николай Михайлович Тихомиров.
В апреле 1896 года император Николай Второй жалует под строительство храма и домов причта участок в одну десятину — то есть чуть больше гектара — земли, которая принадлежала Кабинету Его Императорского Величества.
Авторство проекта храма вызывает у историков архитектуры сомнения и споры. Есть, по крайней мере, три версия, и, по мнению доктора исторических наук, профессора кафедры основ архитектурного проектирования, истории архитектуры и градостроительства НГУАДИ Артемия Туманика, наиболее правдоподобная из них та, по которой автором храма стал авторитетный томский архитектор Константин Лыгин, который ранее построил церковь Пророка Божия Даниила при станции Обь.
Также в тени Лыгина упоминают менее известного в нашем городе архитектора Николая Соловьёва, который, якобы, под началом Лыгина выполнил всю творческую работу.
Часто проект Храма Александра Невского приписывают столичным мастерам Василию Косякову и Дмитрию Пруссаку, которые, возможно, повторно использовали проект Храма Божьей Матери Милующей на Васильевском острове в Санкт-Петербурге. Также возможно, что Константин Лыгин и взял за основу своего проекта работу Косякова и Пруссака.
Освящение церкви состоялось 29 декабря 1899 года. Храм Александра Невского, построенный в византийском стиле, стал не только первой каменной церковью, но едва ли не вообще самым первым каменным зданием в Ново-Николаевском посёлке.