Строительство этой дороги началось одновременно из Владивостока и Челябинска и велось на государственные средства. При этом были продемонстрированы невиданные до того времени темпы железнодорожного строительства. Всего за 10 лет было проложено 7,5 тысячи километров новой железнодорожной магистрали. Но полностью решить данную проблему до конца не удалось. С восточной стороны Транссиб был доведен от Владивостока до Хабаровска. Но затем строительные работы затормозились в связи с необходимостью возведения огромного моста через реку Амур. С западной стороны железнодорожные пути были доведены только до Забайкалья…
Сразу же нужно сказать о том, что данный проект был не столько военно-стратегическим, сколько коммерческим. Русский и европейский капитал кратчайшим путем рвался на Дальний Восток в поисках новых рынков и товаров, и тезис «время – деньги» играл ведущую роль при строительстве Транссибирской железной дороги. Но крупный российский и иностранный капиталы не желали ждать, пока будут преодолены все трудности и реализован данный проект. В результате в середине 90-х годов XIX века появился проект строительства железной дороги на Дальний Восток из Забайкалья через территорию Маньчжурии.
Главным сторонником данного проекта выступил министр финансов С.Ю. Витте, который считал, что эта железная дорога будет содействовать мирному завоеванию Маньчжурии Россией. В пользу маньчжурского варианта сыграло и усиление на Дальнем Востоке активности Японии, угрожавшее интересам Российской империи в Китае. Так было принято решение о сооружении железнодорожной магистрали, получившей название «Китайско-Восточная железная дорога» (КВЖД), которая должна была стать частью Транссибирской железной дороги.
Так как данный проект был коммерческим, то уже при обсуждении планов строительства КВЖД было решено привлечь к участию в нем частный капитал. С этой целью в декабре 1895 года был создан Русско-Китайский банк с первоначальным капиталом в шесть миллионов рублей. При его формировании 15 % средств предоставил Санкт-Петербургский международный коммерческий банк, а 61 % поступил от четырех французских банков. Таким образом, основную роль при строительстве КВЖД играл иностранный капитал, прежде всего французский, который, следовательно, вполне резонно рассчитывал определять политику в данном регионе в будущем.
Правда, дипломатические тонкости, связанные с согласованием всех вопросов, западные капиталисты постарались взвалить на плечи Российской империи. 22 мая 1896 года состоялось подписание секретного (Московского) Российско-китайского договора о союзе этих стран против Японии. Но об истинном характере этого договора можно судить уже по тому, что с российской стороны первую подпись под ним поставили министр финансов С.Ю. Витте, и только затем – министр иностранных дел князь А.Б. Лобанов-Ростовский. С китайской (Цинской) стороны договор подписал министр одной из провинций Цинской империи Ли Хунчжан, который, согласно мемуарам Э.Э. Ухтомского, за это получил от российского правительства взятку в размере трех миллионов рублей. Этот договор предоставил России право на постройку железнодорожной магистрали через территорию Маньчжурии.
После этого события развивались по вполне определенному сценарию. 27 августа 1896 года китайский посланник в Российской империи Сюй Цзэнчэн подписал с правлением Русско-Китайского банка соглашение о предоставлении банку права на постройку железной дороги через Маньчжурию и о создании акционерного «Общества Китайской Восточной железной дороги» со сроком действия 80 лет.
4 декабря того же года устав этого акционерного общества был утвержден Николаем II. После чего сразу же в Петербурге состоялись выборы правления Общества КВЖД. По результатам выборов вице-председателем стал известный инженер-путеец С.И. Кербедз, членами правления – заместитель министра финансов П.М. Романов, руководитель Перербургского международного коммерческого банка А.Ю. Ротштейн, директор Российско-Китайского банка Д.Д. Покотилов и другие видные финансисты. Но формально первым председателем Общества КВЖД, по указу императора Китая, был назначен бывший посланник Цинской империи в Петербурге и Берлине Сюй Цзэнчэн.
Подбором специалистов для прокладки КВЖД руководил лично С.Ю. Витте. По его рекомендации главным инженером этой железной дороги был назначен А.И. Югович, имевший большой опыт строительства Рязанско-Уральской железной дороги. Пунктом расположения Строительного управления по возведению КВЖД был выбран участок на берегу реки Сунгари, в месте ее предполагаемого пересечения с железнодорожной магистралью. Поначалу это место назвали «железнодорожным поселком Сунгари», но впоследствии там возник город Харбин.
24 апреля 1897 года на берега Сунгари прибыл авангардный отряд Строительного управления КВЖД во главе с инженером А.И. Шидловским под охраной пешей Кубанской полусотни есаула Павиевского. Затем в целях охраны строительства КВЖД была создана специальная Охранная стража, позднее преобразованная в Заамурский округ пограничной стражи.