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