Zasadnicze prace nad bryłą budynku zakończyły się w końcu 1898. W świątyni był trzy ołtarze – św. Aleksandra Newskiego, św. Mikołaja Cudotwórcy oraz św. Jerzego Zwycięzcy. Moment poświęcenia obiektu musiał jednak zostać ponownie odłożony, gdyż zabrakło pieniędzy na wykończenie ikonostasu. Ponownie środki na ten cel (6500 rubli) przekazał car. W tym samym czasie trwały prace nad dekoracją wnętrz, w których freski wykonywali artyści z Tomska. Ostatecznie konsekracji cerkwi dokonał 29 grudnia 1899 biskup tomski i barnaułski Makary. Poświęcenie dwóch bocznych ołtarzy miało miejsce dopiero 5 lat później.
Neobizantyński budynek w zamyśle cara miał pełnić funkcję pomnika ku czci jego ojca, cara Aleksandra III. Został zlokalizowany w pobliżu mostu kolejowego. Rangę soboru otrzymał po 1910, kiedy w mieście wzniesiono jeszcze kilka cerkwi prawosławnych, zaś ta ku czci Aleksandra Newskiego była z nich największą. W 1913 obiekt został dodatkowo rozbudowany i otrzymał centralne ogrzewanie i instalację wentylacyjną.
Sobór został zamknięty w latach trzydziestych i do 1988 pełnił różne funkcje świeckie. Już w połowie lat 80. rozważano jego zwrot eparchii nowosybirskiej i berdskiej, jednak prawosławni przejęli obiekt dopiero w 1988.