Одним из первых каменных зданий в Ново-Николаевске был храм Святого Александра Невского. Закладка храма состоялась 15 мая 1897 года. Строительство продолжалось около трех лет, и 29 декабря 1899 года храм был освящен. В сибирском поселке появилось сооружение, построенное в "византийском стиле", гармоничное и пропорциональное. Храм посвящался памяти Александра III, основателя Транссибирского железнодорожного пути. На строительство использовались средства фонда имени Александра III, которые предназначались для возведения церквей и учебных заведений на Транссибирской магистрали.
За собором находился сад, названный в честь императора Александра III в 1912 году. Он имел летний театр и в городе назывался "Сосновка", так как был образован на месте сосновой рощи.