Строительный комитет, заслушав доклады П.П. Мельникова и Н.О. Крафта о результатах изысканий - по "прямому варианту", признал необходимым провести дополнительные работы – с учетом прохождения железнодорожной линии Санкт-Петербург – Москва через Новгород – и поручил это сделать П.П. Мельникову. Выполнив решение комитета, П.П. Мельников пришел к выводу, что строительство железной дороги по "прямому варианту" более выгодно. Вот как сложившаяся ситуация изложена в Путеводителе по Николаевской железной дороге 1914 года:
Государь Император, прочитав доклад, изволил начертать: "Дорогу устроить по прямому направлению, ибо не нахожу ни одной уважительной причины вести ее на Новгород, который не лишится всех выгод, которыми ныне пользуется".
Здесь уместно привести объяснение начальника одного из участков постройки В.А. Панаева по поводу легенды о том, что будто бы Император Николай I, положив линейку на поданную ему карту и проведя линию карандашом, приказал вести железную дорогу по прямой линии. В действительности же дело обстояло таким образом. Как упомянуто было выше, большинство членов комитета по постройке С.-Петербуpro – Московской железной дороги полагало, что надо вести дорогу на Новгород. Государь не разделял этого мнения и, утомленный бесконечными спорами по этому предмету, призвал к себе инженер-полковника Мельникова и спросил его: какого он мнения о направлении дороги. Мельников высказался так: "Дорога должна соединять две весьма населенные столицы; все движение как грузовое, так и пассажирское будет сквозное. В непродолжительном времени должны примкнуть к Москве другие дороги со всех концов России; таким образом, сквозное движение между Петербургом и Москвою разовьется в несколько десятков раз против настоящего. Было бы большою ошибкою и неисчислимою потерею в общей государственной экономии обречь дальнейшие поколения на уплату 80-ти с лишком верст, в продолжение целого века или больше, пока прямой расчет не вынудил бы строить другую, более кратчайшую дорогу от Петербурга до Москвы". "Рад", сказал Государь, "что ты одного со мной мнения, веди дорогу прямо". Слова "веди дорогу прямо" не означали вести по прямой линии, а относились к тому, чтобы не держаться направления на Новгород.
Таким образом, вопрос был решен и линия пошла между двумя столицами по "возможно" прямому направлению. Насколько замечательна прямолинейность С.-Петербурге – Московской железной дороги, можно судить уже потому, что вся длина линии после постройки оказалась в 604 версты, тогда как астрономическое расстояние между Петербургом и Москвою составляет 598 верст, а протяжение Московского шоссе – 674 версты. По окончании изысканий в начале 1843 г., и по собрании всех топографических сведений, линия дороги была нанесена на карту, которая удостоилась Высочайшего утверждения 14 апреля 1843 года и принята к руководству при постройке дороги.
Широкую известность получила легенда о том, что император лично давал указание, как и где проложить дорогу: император приложил к карте линейку и провёл линию. Возле Бологого карандаш, который держала высочайшая рука, наткнулся на палец другой высочайшей руки и прочертил изгиб. Императорские решение надлежало выполнить. В действительности, если не брать во внимание некоторые кривые большого радиуса, имеющиеся на дороге и поныне, а также кривые меньшего радиуса в горловинах станций, реконструируемые сейчас под скоростное движение, изначально дорога была построена совершенно прямой. В месте упомянутого изгиба — в районе станции Мстинский мост — линия также была абсолютно прямой, что при имеющемся в этом месте перепаде профиля, затрудняло движение составов, движимых маломощными паровозами. Для прохода подъёма приходилось вцеплять дополнительный локомотив. Ради преодоления неудобств путём уменьшения перепада профиля и был создан «изгиб» — Веребьинский обход со ст. Оксочи. Через много десятилетий после того, как необходимость в таком «серпантине» отпала, Веребьинский обход был демонтирован, станция Оксочи — закрыта, а линия вновь стала прямой.
Работы по сооружению дороги начали 27 мая 1843 г. одновременно с двух сторон – от Санкт-Петербурга до Бологого (Северная дирекция) и от Москвы до Бологого (Южная дирекция). Начальниками дирекций назначили авторов проекта – П.П. Мельникова (Северная) и И.О. Крафта (Южная). Для приближения дирекций к месту строительства их разместили соответственно в Чудове и в Вышнем Волочке (позже Южная дирекция была переведена в Тверь).
Строили дорогу строительные артели, куда входили главным образом крепостные крестьяне, находящиеся в прямой зависимости друг от друга: в случае заболевания рабочего вычеты на его содержание осуществлялись из заработка всей артели. Многие из строителей дороги погибли от тяжелых условий труда, скудного питания, эпидемий холеры, чумы и тифа. В отдельные годы на строительстве работало до 63 тысяч человек. Основными орудиями их труда были кирка, лопата и тачка, применялась также и конная возка.
Работы разворачивались от опорных пунктов, которые размещались в зонах примыкания трассы к водным путям сообщения. Через эти пункты строительные участки снабжались материалами и оборудованием. В районе Валдайской возвышенности земляные работы выполнялись с помощью четырех паровых землекопных машин, приобретенных в Соединенных Северо-Американских Штатах.
Дорога строилась сразу на два пути протяженностью 644 км с шириной колеи 1524 мм, принятой на американских железных дорогах, в отличие от европейских – с более узкой колеёй. Путь наряду с поперечными шпалами имел еще продольные лежни, уложенные под рельсы. Довольно скоро от них отказались; еловые шпалы, служившие четыре года, заменялись сосновыми, а в 1886 г. их стали пропитывать хлористым цинком, что давало увеличение срока службы до 7-8 лет.
Ширина колеи в 1 524 мм впервые стала использоваться в России в ходе постройки Николаевской железной дороги. Возможно, это было связано с тем, что на строительстве работали консультанты из Америки, и прежде всего Дж. В. Уистлер (в то время эта колея была популярна в южных штатах США). Возможно также, что использовать эту ширину колеи предложили русские инженеры П. П. Мельников и Н. О. Крафт, посетившие Америку перед началом строительства Николаевской железной дороги. Кроме того, эта ширина колеи была удобна тем, что выражалась круглым числом – 5 футов. Существует распространённое мнение, что при выборе ширины колеи сыграл роль и военный аспект — отличная от европейской ширина колеи затруднила бы гипотетическому противнику снабжение войск в случае вторжения в Россию. Никаких документальных подтверждений этой версии не имеется. С середины XIX века стандартом на железных дорогах России (позже – СССР), Финляндии и Монголии была ширина колеи 1 524 мм. С мая 1970 года до начала 1990-х годов железные дороги СССР были переведены на колею 1 520 мм. Это было сделано с целью увеличить стабильность пути при эксплуатации товарных поездов, повысить их скорость движения без модернизации самого подвижного состава. После распада СССР это – стандарт ширины колеи на железных дорогах всех стран, образовавшихся на его месте. Железные дороги Финляндии до настоящего времени продолжают использовать прежний стандарт – 1 524 мм.
Разница в 4 мм не требует переоборудования подвижного состава, но на переходном этапе вызвала серьёзные проблемы с резко увеличившимся износом колёсных пар подвижного состава. Впрочем, до конца взаимосвязь ширины колеи или, более корректно, зазора между внутренними гранями рельсов и гребней колёс колёсной пары с интенсивностью изнашивания рельсов и гребней колёс установить не удалось.
Первые рельсы были железными, имели вес 27,8 кг в погонном метре и были изготовлены английской фирмой Виньоля. В 1870-е гг. на опытном участке в районе станции Веребье начали испытания рельсов со стальными головками. В начале 1880-х гг. перешли к изготовлению рельсов из стального проката с постепенной заменой железных по всей магистрали.
Так как дорога строилась по прямому варианту и пересекала множество рек и оврагов, на ней возвели 278 искусственных сооружений, в том числе 184 моста, 69 каменных и чугунных труб и 19 путепроводов. Строителями крупных деревянных мостов были: Д.И. Журавский (Веребьинский мост протяженностью 500 м с высотой опор 50 м),
Журавский разработал теорию ферм и их расчётов. В 1856 году Кербедз построил по его методу для Петербургско-Варшавской железной дороги мост из сквозных металлических ферм через р. Лугу. Это был первый в мире мост, построенный на теоретических расчётах. С появлением работ Журавского и последовавших за ними других исследований началось строительство тех лёгких, ажурных мостов с огромными пролётами, вступая на которые, водитель поезда не снижает скорости, а пассажирам не приходит в голову и мысли об опасности.
Все большие и средние мосты имели деревянные решетчатые фермы систем Гау-Журавского. Позже за теорию расчета мостовых ферм Д.И. Журавский получил полную Демидовскую премию.
На линии Санкт-Петербург – Москва всего было построено 34 станции четырех классов: I класса – пять станций, из которых две столичные в Санкт-Петербурге.