Витте несомненно был превосходным дипломатом, и его стратегия сработала. Китайцы дали разрешение на строительство дороги, которая должна была проходить по прямому пути от Читы, расположенной в 400 км к востоку от Байкала, до Владивостока. Но Ли не согласился на то, чтобы стройка велась полностью за счет российского государства. Вместо этого была разработана схема, согласно которой строительство линии должна была осуществлять якобы частная компания, «Акционерное общество Китайской Восточной железной дороги», которое, как подчеркивает в своих воспоминаниях Витте, находилось «полностью в руках правительства»[68]. Более того, номинально являясь частной корпорацией, общество «находилось в ведении Министерства финансов» — другими словами, в ведении самого Витте. Китай согласился предоставить полосу отчуждения, достаточную для строительства и эксплуатации железной дороги, а также землю для сооружения запасных путей, депо и станций. И, что примечательно, для железной дороги была создана особая экстерриториальная полиция, обладавшая «полной и неограниченной властью». Со своей стороны, китайцы настаивали на том, чтобы русские не заходили южнее железнодорожной линии. Витте с готовностью согласился с этим требованием, но данное обещание была нарушено почти сразу же после начала строительства.

Все переговоры велись в строжайшей тайне, к вящему удовлетворению Витте: «Ни одного слова не было проронено об этом секретном, чрезвычайно важном соглашении, которое тогда было заключено Россией с Китаем». Ли, по-видимому, был также заинтересован в сохранении секретности. Договор оказался чрезвычайно выгодным для России (что признавал и Витте), и позднее по этой причине строящаяся дорога сильно пострадала в результате Ихэтуаньского (Боксерского) восстания (1899-1901). Русские получили право эксплуатировать дорогу сроком на 36 лет, но и по истечении этого срока китайцам пришлось дорого заплатить за то, чтобы вернуть это право себе. По признанию самого Витте, на 37-й год возвращение контроля над дорогой обошлось бы в 700 миллионов рублей. Хотя договор можно рассматривать как часть захватнической политики Российской империи[69], Витте категорически это отрицал. «Ни при каких обстоятельствах Транссибирская магистраль не станет служить средством территориальной экспансии», — писал он. Однако даже если это и было правдой, Япония, вне всякого сомнения, восприняла решение о строительстве Китайско-восточной железной дороги совсем иначе. На деле железная дорога являлась источником геополитического напряжения между тремя империями и со временем привела к территориальным спорам и даже военным конфликтам.

Первый участок Транссибирской магистрали, где вновь (после неудачной попытки старта в 1891 году) должны были начаться строительные работы, пролегал в окрестностях Челябинска, самого восточного пункта существовавшей на тот момент железной дороги. Он расположен примерно в 190 км к югу от Екатеринбурга, которому теперь предстояло стать воротами в Сибирь. На обычных линиях строительными работами руководил специально назначенный инженер, который либо сам занимался всеми организационными вопросами, либо, что случалось чаще, привлекал подрядчиков. Большинство подрядчиков стремились нанять сотни и даже тысячи рабочих, хотя случалось, что для выполнения некоторых задач было достаточно и небольших артелей. Первый участок — Западно-Сибирский отрезок, протянувшийся от Челябинска до берега реки Оби, противоположного тому, на котором располагался Новониколаевск. Этот город возник в 1893 году в ходе строительства Великого Сибирского пути и был назван в честь царя и его святого покровителя Николая Угодника — для защиты как на земле, так и на небесах. В советские времена переименован в Новосибирск.

Чтобы облегчить процесс управления, длинный Западно-Сибирский отрезок примерно посередине — в Омске — был поделен на два участка. Начальником работ по строительству Западно-Сибирской дороги был назначен Константин Яковлевич Михайловский, дворянин украинского происхождения и ветеран Крымской войны, опытный гражданский инженер, построивший Александровский мост через Волгу, открытие которого состоялось в 1880 году. В качестве документации Михайловский получил карту, на которой была прочерчена тонкая прямая линия, тянущаяся через степи на расстояние примерно 1450 км. Хармон Таппер так описывает этот момент: «Он был готов к суровым морозам, ограничивающим рабочий сезон четырьмя месяцами, но не ожидал столь острого дефицита вагонов, телег, лошадей, барж и пароходов». На Западном отрезке, где на протяжении столетий земля была схвачена вечной мерзлотой, наибольшие трудности создавал недостаток лесоматериалов, поскольку на всю округу был только один подходящий лес, да и тот находился в 320 км к востоку от Челябинска. В результате большая часть лесоматериала завозилась из удаленных частей Европейской России, как и рельсы, и другие промышленные изделия.

Остальные материалы можно было достать на месте, пусть по высокой цене, но ощущался недостаток рабочей силы, особенно опытных и квалифицированных рабочих, что создавало наибольшие трудности для подрядчиков. В процессе реализации проекта спрос на рабочую силу всегда превышал возможности края. Уровень механизации работ, только недавно ставший обычным элементом железнодорожного строительства в Европе и Америке, был крайне низок, и поэтому Комитет Сибирской железной дороги подсчитал, что для реализации первого этапа, включавшего Западную и Среднесибирскую линии, потребуется 30 000 чернорабочих для земляных работ и еще 50 000 квалифицированных и неквалифицированных рабочих для выполнения остальных видов работ. Хотя на первом отрезке пути неквалифицированная рабочая сила была более доступна, чем при продвижении дальше на восток — на месте вербовалось около 80% рабочих, — мастеровых среди них было мало. Как пишет Таппер: «Даже в сравнительно густонаселенных сельскохозяйственных районах между Челябинском и Омском трудно было найти квалифицированных рабочих, поскольку крестьяне не обладали необходимыми техническими навыками. В краю бескрайних пастбищ скотоводы-кочевники отказывались покидать свои стада, которые они ценили настолько высоко, что при встрече у них было принято вежливо интересоваться здоровьем скотины, а не домочадцев собеседника)». Привлечение к работе на стройке местного населения имело еще один недостаток: в сезон сбора урожая крестьяне стремились вернуться домой, и их не интересовала судьба железной дороги, в результате чего в наиболее оптимальный для строительства период возникал дефицит рабочей силы. Вследствие этого подрядчики Михайловского были вынуждены искать рабочих не только в Европейской России, но и в Турции, Персии и Италии.