В том же году знаменательном не только для Императора , в далекой Сибири в поселке Новониколаевске ,названного в честь благополучно царствующего Государя Императора, идет закладка железнодорожного моста , после чего жизнь его стремительно меняется. Подтверждением этого является запись в журнале «Нива» (1898г.): « Проведение великой Сибирской железной дороги так изменило картину Сибири, и так отразилось на некоторых населенных пунктах, что невольно приходится изумляться. К одному из таких центров, поражающих чисто американским ростом , следует отнести поселок Новониколаевский». Ново-Николаевский поселок//Нива. ( -1898.-№ 31.-С.614-616).

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

Годом спустя, в хмурый, осенний день на «всеобщем сходе», испросив благословление епископа Томского и Барнаульского Макария , задумали новониколаевцы церковь строить во имя святого благоверного князя Александра Невского.

 Пестрит толпа , шевелится, блуждают глаза среди разных лиц: от совсем юных весельчаков , с тонким , неровно, пробившимся пушком на пухлых, румяных щеках, и, до весьма значительных в летах, степенных мужиков ,с опытом прожитых лет во взгляде, не терпящих , казалось пререканий ;были здесь и совсем уж старцы с глубокими морщинами и складочками на переносье .

Колючий воздух, наполненный первыми морозами, кусает за легкие и выходит из оживленных ртов клубами теплого пара споров, волнений, упорств.

Наконец порешили: организовали комитет во главе с начальником строительства Среднесибирского участка железной дороги Н.Г. Межениновым. А самых шустрых и смекалистые крестьян в подмогу выдвинули Илью Титлянова, да Дмитрия Налимова. Придумал тогда староста Титлянов организовать сборы пожертвований для сооружения храма. Собрать по рублю с каждого владельца усадьбы и 30 копеек со всех жителей. А чтобы храм приметен был решили расположить его на высоком берегу Оби, возле железнодорожного моста , чтобы горделиво и могущественно вознесся он своими злаченными куполами. И виден был как из проезжающих поездов, так и с подплывающих к пристани пароходов.

 В апреле 1896 года император Николай II жалует под строительство храма и домов причта участок земли в одну десятину (2 400 кв. саженей) земли, принадлежащей Кабинету Его Величества. Из фонда строительства церквей было выделено 47 тысяч рублей на постройку церкви Александра Невского в Новониколаевске. Из выделенных денег 19 тысяч рублей приходилось на долю московских купцов первой гильдии Баевых. Так же , на строительство храма император лично пожертвовал 5 000 рублей и позже еще 6 500 - на изготовление иконостаса.

Цветет весной май, торжественно шествуя по Сибирской земле, торопливо пробуждая дремлющую , после зимней спячки природу; расцветает и духовная жизнь новониколаевцев.

15 числа сего месяца в 1897 году состоялся торжественный молебен по случаю закладки каменного храма. Основательно готовились жители города к такому знаменательному событию: трепетно и благоговейно ожидали прибытие епископа и высоких гостей.

В точно назначенный час епископ, окруженный сонмом духовенства, в присутствии Томского губернатора А. Ломачевского, уже известного нам Н. Меженинова и инженера В. Линка, совершает необыкновенное таинство. Благоговейно замерев, многочисленные миряне , взволнованно созерцают священнодействие, внимая святым молитвам священника.

Важно шествует почтенный епископ в почтительном сопровождении братии Христовой, совершает водосвятие, окропив место будущего алтаря храма, и освещает камень, служащий его основанием, читая молитву: "Основывается церковь сия во славу Великого Бога и Спаса нашего Иисуса Христа, в честь оберегателя и защитника земли русской, святого благоверного князя Александра Невского, во имя Отца и Сына и Святого Духа. Аминь."

Возливает святейший елей на камень. Певчий клир запевает стихиру на положение камня, мысленно унося нас в ветхозаветные времена к патриарху Иакову, который встав заутра и взяв камень, его же бе положив в возглавие себе, и постави столп, и возлил елей верху его, рече:"... яко есть Господь на месте сем, аз же не ведех: страшно есть место сие, несть сие, но Дом Божий, и сия суть врата небесная ".

Возгорается Божья Искра в месте сем, освящая вокруг все Светом невидимым , а сердца присутствующих благодатью Божьей.

К концу 1898 года кладка кирпичных стен церкви была закончена. В ней было три престола: главный придел во имя святого благоверного князя Александра Невского и два боковых — во имя Святителя Николая Чудотворца и во имя святого великомученика Георгия Победоносца. Роспись церкви выполнила томская иконописная мастерская И. А. Панкрышева. Собор, по свидетельствам современников, имел богатое оснащение. Ризницу украшали парчовые облачения для священнослужителей, а также образ Георгия Победоносца, пожалованный императрицей Марией Фёдоровной.

7 декабря 1899 года государь подарил священническое и диаконское облачения, сшитые из весьма ценной золотой парчи, которая служила покровом на гроб великого князя Георгия Александровича. Также он передал в дар храму иконы афонского письма: Иверская икона Божией Матери и икона св. вмч. Пантелеимона Целителя.

Образцом зодчему Н. Соловьеву послужила центричная структура, известная по петербургским проектам многих храмостроителей. Но в отличии от известных прототипов архитектор увеличил диаметр центральной главы и приподнял ее над объемами окружавших с четырех сторон апсид несколько выше, чем было принято ранее в храмах этой типологической группы. Композиция церкви дополнялась звонницей над главным входом.

 
В сибирском поселке появилось сооружение, построенное в «византийском стиле», гармоничное и пропорциональное, что выдавало принадлежность его автора к петербургской архитектурной школе.

Фасады обильно украшены узорными карнизами из профильного кирпича, места сочленения стен и кровли - зубчатыми поясами на нижнем уровне восьмиконечника и на барабане между окнами, арками над окнами и в звоннице. Средняя часть объема, в плане представляющего крест, обильно декорирована уступчатыми нишами также в форме креста. Большие окна светового барабана прорезают массивный объем, давая возможность осветить внутреннюю часть собора. Тема полукруглой арки, начатая на звоннице, повторяется на всех уровнях собора и завершается куполом - основной композиционной осью храма.

Окончание строительства Александро-Невской церкви и освящение ее 29 декабря 1899 года епископом Томским и Барнаульским Макарием, можно считать одним из самых больших успехов церковного строительства в Сибири. Церковь была самой большой и красивой из всех церквей, построенных из средств фонда Александра III, и размещалась на высоком берегу Оби.

На территории прихода церкви размещались учебные заведения: реальное училище имени Дома Романовых, женская гимназия, учительская семинария, городское четырехклассное училище и 10 школ (одна из них церковно-приходская).

В феврале 1910 года храм во имя святого благоверного князя Александра Невского стал центром благочиния новониколаевских церквей. В городе Новониколаевске действовали на 1911 год следующие православные храмы: в Вокзальной части — Пророко-Данииловская церковь; в Центральной части — Александро-Невская церковь, Покровская церковь и Воскресенская церковь; в Закаменской части — Богородице-Казанская церковь. В военном городке в 1913 году была построена Преображенская церковь. В 1915 году храму Александра Невского присваивают статус собора.

Много пережил собор за свою жизнь: и попытки взрыва в 1937 году , страшные разрушения и зверские переоборудования то в институт, то киностудию, то в филармонию. И все же в эти горькие и мучительные периоды советского режима «безбожной власти», не в силах сопротивляться ей, безмолвно и стойко переживая форсированные атаки и массовый террор духовенства, он выжил , выстоял, живя Искрой Божьей в Душах и Сердцах верующих. А в 1988 году Собор Святого Благоверного Князя Александра Невского вновь передан Русской православной церкви.