Проект дороги был утвержден 21 декабря 1835 года. Строительство началось в мае с загородного участка трассы; вблизи Петербурга строительные работы долго не удавалось начать из-за всевозможных проволочек, связанных с покупкой частных земель.
Первый участок железной дороги, между Павловском и Царским Селом, был окончен раньше, и движение по нему открылось 27 сентября 1836 года. Так как купленные в Англии паровозы еще не прибыли, то вагоны перемещались лошадьми. В октябре из Англии на паруснике доставили в разобранном виде первый паровоз. Его по частям перевезли в Царское Село и здесь собрали. 6 ноября 1836 года из Царского Села в Павловск, при огромном стечении зрителей, отправился первый поезд на паровозной тяге.
Весной 1837 года развернулись строительные работы на участке дороги вблизи Петербурга.
Торжественное открытие железной дороги, связавшей Петербург с Павловском, состоялось 30 октября 1837 года.
Первая русская железная дорога не имела большого экономического значения, но дала первый опыт инженерам и строителям и доказала преимущества нового вида транспорта.
Опасаясь — и не без оснований, — что небольшой поток пассажиров сделает эксплуатацию дороги Петербург-Павловск экономически невыгодной, Герстнер предложил у ее конечной станции построить для привлечения публики здание воксала — так называли тогда разного рода увеселительные заведения, предназначенные для отдыха и развлечения. В итоге конкурса на проект здания воксала, проведенного весной 1836 года, был выбран проект, составленный архитектором А. И. Штакеншнейдером.
В летние месяцы павловский воксал становился одним из главных центров музыкальной жизни Петербурга. Устраивавшиеся здесь концерты привлекали многочисленную публику. Интересный репертуар, первоклассные исполнители, хорошая акустика зала — все это удачно сочеталось с возможностью прекрасной прогулки по аллеям прославленного парка.
Поскольку увеселительный воксал в Павловске, размещенный вблизи железнодорожных путей, одновременно являлся и конечной станцией, то его название постепенно утратило свое первоначальное значение и стало связываться с железной дорогой. Старое слово «воксал», превратившись в «вокзал», изменило и свой смысл: вокзалами стали называть большие пассажирские здания на всех железных дорогах России.
Конечная станция в Петербурге была размещена на западном участке плаца Семеновского полка: около пересечения Загородного проспекта с Введенским каналом. Первоначально станционное здание было деревянным, одноэтажным и, по мнению современников, «весьма неприглядным». Новое каменное здание было построено в 1849–1851 годах по проекту К. А. Тона. Его планировка в виде буквы П, охватывающей конец железнодорожных путей, стала впоследствии типичной для вокзалов так называемого тупикового типа. Главный фасад выходил на Загородный проспект. Ничего специфически «вокзального» в облике главного фасада не было: стены были прорезаны окнами обычных размеров, охваченными наличниками ренессансного типа, и только большие подъезды с арочными навесами на чугунных колоннах намекали на транспортную функцию здания. Более оригинально выглядел боковой фасад: он представлял собой мощную девятипролетную аркаду, сквозь проемы которой пять лестниц вели с площади на платформу. В середине 1870-х годов вокзал был увеличен, при этом его лицевой корпус был удлинен и получил новую, более нарядную отделку. В начале XX века дорогу продлили до Витебска, и тогда же соорудили ныне существующий Витебский вокзал.