Прежние названия:
до 1909 — Обь
до 1926 — Новониколаевск
Количество путей: 14
Архитектура здания предполагалась лаконичной, в стилистике конструктивизма. В объёмно-пространственном решении вокзала можно угадать образ мчащегося на восток паровоза. Арочно-сводчатое перекрытие вокзала предполагалось продлить над путями станции в виде конкорса, в котором должны были разместиться зал ожидания с рестораном, с лестницами к перронам.
В июле 1930 года городская планировочная комиссия внесла в проект ряд изменений. Дальнейшая разработка проекта была поручена киевскому отделению Гипротранса. По рабочему проекту из Киева в 1931 году были заложены фундаменты вокзала. Однако теперь архитектурный облик вокзала вызывает сомнение у руководства треста «Сибстройпуть». Проект перерабатывался ещё несколько раз, вначале Б. А. Гордеевым, затем Г. Б. Бархиным и А. 3. Гринбергом; по их схеме в Сибирском отделении «Стандартгорпроекта» был составлен окончательный проект. Уникальную арочную конструкцию центрального зала разработал знаменитый инженер Николай Никитин.
После директивного изменения «стилистической направленности советской архитектуры» в Новосибирске был проведён конкурс на внешнюю архитектуру фасадов вокзала. В итоговом проекте центральная часть вокзала имеет композицию триумфальной арки, обрамлённой пилястрами тосканского ордера и увенчанной большим аттиком, скрывающим снаружи железобетонную параболу свода главного кассового зала.
Вокзал был принят Государственной комиссией в эксплуатацию 25 января 1939 года.
В 1997—2000 годах был закончен капитальный ремонт здания по проекту института «Сибжелдорпроект». Обновлены фасады, для облицовки стен и пола были использованы природные материалы — гранит и мрамор.
В 2005 году к югу от главного здания вокзала построен пригородный павильон.