Каменное здание железнодорожного вокзала было построено в 1896-1907 годах. 16 июня 1895 года в «Вологодских губернских ведомостях» сообщалось следующее:
|
«На станции “Вологда”, взамен существующего деревянного пассажирского здания, будет возведён на новом месте, по продолжению Желвунцовской улицы, каменный вокзал гораздо больших размеров; теперешний же предназначается исключительно под товарную станцию» | 
|
После постройки вокзал неоднократно расширялся, а в 1987—1988 годах здание было реконструировано.
Существует мнение [1], что изначально каменное здание железнодорожного вокзала было полностью построено в 1896 году. Возможно даже, к открытию движения Вологда-Кубино 1 августа 1896 года. К 1905 году назрела необходимость расширения, так как не все недочеты первого проекта удалось устранить (первоначально был утвержден только 2 проект, так как к 1 проекту нашлось 15 замечаний, благодаря которым вокзал стал не симметричным). В 1905 году был составлен уже 3 проект, предусматривающий 2-этажную пристройку слева (если смотреть со стороны путей) для размещения почты и прочих служб.
