На Всесоюзный конкурс эскизных проектов новосибирского вокзала, организованный Московским архитектурным обществом в 1929 г., поступило 45 проектов, 12 из которых были премированы. Первую премию получил проект архитектора Н.Г. Волошинова, но проект на выставке в Новосибирске в июле 1930 г. подвергся резкой критике, и городская планировочная комиссия внесла в него ряд корректив. В заключении комиссии отмечалась недостаточная площадь вестибюля, кассового зала и багажного отделения, удалённость камер хранения ручной клади от входов в вокзал. Вместе с этим комиссия высказала неудовлетворение «архитектурным оформлением здания», утверждая, что сооружение в проекте «скорее походит на конструкцию коробки для производственных зданий», чем для пассажирского вокзала. Дальнейшая разработка эскизного проекта Н.Г. Волошинова была поручена киевскому отделению Гипротранса, где проект сооружения претерпел значительную трансформацию. По рабочему проекту из Киева и были заложены фундаменты вокзала.

Однако скоро монолитные железобетонные рамные конструкции, плоские крыши и вообще архитектурный облик вокзала вызвали сомнения у технического руководства «Сибстройпути». Начались новые пересмотры проекта, а затем «Сибстройпуть» поручил архитектору Б.А. Гордееву составление коррективного эскизного проекта вокзала. Проект Б.А. Гордеева подвергся экспертизе архитекторов Г.Б. Бархина и А.3. Гринберга; они не только рецензировали проект, но и предложили так называемую «схему А», по которой Сибирское отделение «Стандартгорпроекта» составило окончательный проект вокзала в Новосибирске на 4 тыс. пассажиров.
Здание вокзала возводилось в течение 1932-1939 гг. 25 января 1939 г. Государственная комиссия приняла его в эксплуатацию. В процессе строительства в разработке многих его элементов, интерьеров, фасадов участвовали архитекторы А.И. Лоскутов, М.П. Клековкин, Б.П. Савельев, И.С. Персиков, К.И. Митин, Я.Е. Кузнецов, А.Д. Крячков при общем руководстве Б.А. Гордеева, С.П. Тургенева и Б.А. Биткина.

Архитектура вокзала по сравнению с первоначальным конкурсным проектом претерпела значительные изменения — через конструктивистскую архитектуру по киевскому проекту, через ряд вариантов в формах схематизированного и упрощённого классицизма до окончательного весьма эклектичного варианта с различно прорисованными деталями — ближе или дальше от приёмов ордерной архитектуры. «Улучшать» архитектуру вокзала представлялось весьма сложным делом. Железобетонные, монолитные конструкции, возведённые по киевскому проекту, нужно было трансформировать в разнообразные формы ордерной архитектуры, которые уже прочно вошли в творческую практику архитекторов.

Центральная часть вокзала приобрела композицию типа триумфальной арки, обрамлённой пилястрами «тосканского» ордера и увенчанной большим аттиком, скрывающим снаружи железобетонную параболу свода главного кассового зала. Крупные ордерные формы и арка витража центральной части фасада не гармонируют с боковыми его частями, измельчёнными деталями. Но главный недостаток архитектурной композиции вокзала заключается в том, что его невозможно визуально охватить в целом со стороны площади, хотя по проекту вся гармония его архитектуры строилась именно на таком восприятии. Здание имеет трёхчастное классицистическое членение фасада, но цокольная крупно рустованная часть фасада скрыта для наблюдения с привокзальной площади резким перепадом рельефа, а при близком рассмотрении сильные ракурсы здания не позволяют увидеть композицию в целом.

На общий характер декоративных приёмов в здании вокзала оказала влияние архитектура здания Театра оперы и балета. И естественно, что оба этих крупнейших сооружения Новосибирска первых пятилеток, в проектировании которых участвовали ведущие архитектурные силы, оказали, в свою очередь, влияние на всю архитектуру города 30-х годов.

С.Н. Баландин, «Новосибирск. История градостроительства 1893 – 1945».