Рассмотрев предложения Мельникова, царь счёл их убедительными. Из-за этого при обсуждении проекта строительства стратегической Петербургско-Московской железной дороги был отвергнут план графа Бобринского, предлагавшего получить банковский займа в Германии и вновь пригласить иностранных специалистов. Напротив, проект Мельникова и его сотрудника Николая Крафта предполагал строительство линии за счёт казны. Новаторским по тем временам был и сам процесс строительства: параллельно с полотном строились системы обеспечения дороги. Впервые был применён унифицированный порядок организации пути. Это означало, что через каждые 20–40 км располагалась платформа, созданная по стандартному образцу, а через каждые 80 км — пассажирская станция с буфетом и залом ожидания. Расчётная стоимость строительства составляла 70 тысяч рублей (или примерно 150 миллионов современных) за километр.

Павел Мельников (слева) и Николай Крафт (справа) стояли у истоков современных российских железных дорог

Новая железная дорога ставила перед собой амбициозную задачу перевозки 200 тысяч пассажиров и 400 тысяч тонн грузов в год. Для её реализации Мельников и Крафт привлекли команду молодых инженеров-путейцев. В частности, среди них был Николай Миклуха, отец знаменитого этнолога и путешественника, отвечавший за самый сложный, новгородский участок строительства. Работы начались в марте 1843 года сразу с двух сторон: с севера на юг от Чудова и с юга на север — от Твери. Консультантом строительства выступал американский инженер Джордж Уистлер, который привёз с собой новейшую строительную технику, в частности, паровой экскаватор.

Стремясь сделать дорогу полностью государственной, Мельников и Крафт не учли одной вещи, а именно системной коррупции николаевской России. В деле строительства Петербургско-Московской железной дороги она выразилась в облике куратора проекта, графа Петра Клейнмихеля, имевшего репутацию главного взяточника своего времени. Зная, что отечественные предприятия не справляются с большим заказом на производство рельсов (более 80 тысяч тонн!), Клейнмихель стал закупать их в Англии, затратив на это порядка 4 миллионов рублей (или около 10 миллиардов современных). При этом привезённые из Англии рельсы просто лежали без использования, и в итоге оказалось выгоднее дождаться отечественных. Госзаказ на поставку креплений для рельсов на сумму более миллиона рублей (или более 2,5 миллиарда современных) по совпадению выиграл племянник Клейнмихеля, который к тому же использовал для его выполнения государственные предприятия.

Граф Пётр Клейнмихель — злой гений железнодорожного строительства

Используя административный ресурс, Клейнмихель не задумываясь обманывал подрядчиков. Так, известно, что сотрудники министра, офицеры путей сообщения, не выдавали подрядчикам квитанции на получение денег за выполненную работу без «откатов», доходивших до 50 % от суммы. Из-за этого подрядчики не могли расплатиться с субподрядчиками, так как не имели на руках достаточно наличности, что провоцировало конфликты. Если подрядчик собирался жаловаться в жандармское управление за неполучение денег за объект, его ставили перед фактом, что по бумагам никого объекта нет, хотя в реальности он мог уже годами эксплуатироваться. В других случаях представители генподрядчика (то есть Министерства путей сообщения) получали в казне сумму на очередной этап строительства и держали её не у себя на балансе, а в коммерческом банке, параллельно получая неучтённые проценты.

Строительство железной дороги из Петербурга в Москву на литографии того времени

Сам Клейнмихель за солидный «откат» сдал Александровский завод в Петербурге в шестилетнюю аренду американскому предпринимателю Уильяму Льюису Вайненсу, обязавшемуся производить ремонтные работы на Петербургско-Московской железной дороге. Согласно одному из пунктов контракта, поезда по ней не должны были превышать низкий лимит скорости, в противном случае Вайненсу начислялась страховая доплата за риск. Поскольку график движения поездов не укладывался в данный лимит, по истечении срока аренды Вайненс выставил претензию на общую сумму 3,5 миллиона рублей (свыше 7 миллиардов современных), которую российским властям пришлось погасить. В итоге первоначальная стоимость Петербургско-Московской железной дороги была превышена более чем в два раза.