На Меженинова также оказывалось давление. Витте и сформированный им комитет были так впечатлены успехами Михайловского, что решили перенести дату завершения строительства линии в целом на 1899 год, пускай даже с необходимостью паромного сообщения на крупных реках и озере Байкал. Меженинов сначала надеялся продвинуться дальше на восток, закончив первый отрезок от Оби до Красноярска на Енисее, а затем начать работать над прокладкой оставшейся части маршрута до Иркутска. Однако настойчивые требования Витте ускорить строительство означали, что Среднесибирская дорога должна быть закончена через пять, а не через семь лет, и это вынудило Меженинова начать работы на втором участке раньше, чем планировалось. Более того, он предполагал начать работы сразу с двух концов, но запоздалое исследование Ангары, вытекающей из озера Байкал в районе Иркутска, по которой должна была осуществляться доставка рельсов и стройматериалов, выявило, что из-за отмелей и порогов река непроходима для барж. Трудности усугублялись банкротством литейной мастерской в Иркутске, которая, как надеялся Меженинов, должна была поставлять рельсы. В результате он решил начать работы силами только одной группы, двигаясь на восток от Красноярска.
В свете всех этих трудностей нет ничего удивительного в том, что именно на Среднесибирском участке строителям чаще всего приходилось идти в обход правил. Недостаточное снабжение, с одной стороны, и требование строить как можно быстрее — с другой, привели к тому, что все делалось кое-как. Меженинов, прокладывая дорогу, вынужден был руководствоваться соображениями экономии, намеренно уменьшая радиус поворотов и крутизну уклонов. Насыпи сооружались уже и ниже, чем того требовала технология; балластный слой был слишком тонким, а вес рельсов, составлявший менее 22 кг на метр, был примерно на треть меньше веса стандартных рельсов, использовавшихся при строительстве железных дорог в Европе и Америке. Все это означало проблемы в будущем, и в первые годы эксплуатация Транссиба сопровождалась почти непрерывной чередой ремонтных работ и требовала постоянного вложения средств в устранение недостатков, допущенных при строительстве линии.
Тем не менее Меженинов сумел сделать то, что многие критически настроенные инженеры на Западе сочли бы невозможным. Он построил Среднесибирскую железную дорогу — от Оби, где стремительно рос и развивался Новониколаевск, до Ангары, на противоположном берегу которой находился Иркутск, — всего за пять лет, что означало 320 км в год, и это было тем более впечатляюще, что экстремальные условия оставляли слишком мало времени на укладку путей. К тому же Меженинов попутно построил, несмотря на сложный рельеф местности, ветку до Томска протяженностью 71 км, на что ему понадобилось полтора года. Расходы на строительство ветки, к удовольствию комитета, покрылись за счет средств, сэкономленных Михайловским на Западно-Сибирской линии.
Первый участок Среднесибирской дороги — от Новониколаевска до Красноярска — был открыт в январе 1898 года, а годом позже регулярное сообщение осуществлялось уже на всем пути до Иркутска, что намного опережало намеченный на середину 1900 года срок окончания строительства. В то время как Михайловскому удалось осуществить строительство вверенного ему участка, не выходя за рамки бюджета, расходы на Среднесибирскую линию, несмотря на экономию, намного превысили ожидаемые, что, в общем-то, было неудивительно. Даже еда для рабочих и корм для лошадей в процессе строительства подорожали втрое, но не из-за выросшего спроса, а по причине неурожая, разразившегося в районе стройки, в то время как остальные ресурсы стоили дорого вследствие их нехватки и расстояния, на которое их приходилось перевозить. Сам факт наличия большого количества рабочих неизбежно вел к повышению цен на продукты, поскольку местные поставщики не упускали шанса нажиться. Как следствие, приходилось повышать жалованье рабочим, чтобы дать им возможность нормально питаться, и, учитывая все эти трудности, оставалось только удивляться, что проект не вышел за рамки сметы еще больше.