Projektowanie w terenie rozpoczęto w 1897 roku, a budowę – wiosną 1898 roku. Głównym inżynierem był A. Jugowicz, zastępcą S. Ignacius. Pierwszy odcinek Manzhouli – Harbin otwarto w 1899 roku. W 1903 ukończono całość linii, łącznie z południową odnogą od Harbinu do rosyjskich baz morskich Dalnyj (Dalian) i Port Artur (ob. Lüshunkou). Kolej była początkowo jednotorowa, na jej trasie zbudowano 1464 mostów i 9 tuneli. Długość wynosiła 2269 wiorst (2420 km). W 1913 roku kolej dysponowała 367 parowozami, 2696 wagonami towarowymi i 903 pasażerskimi. Towarzystwo KWŻD dysponowało także 20 statkami, odbywającymi rejsy z Władywostoku. Oprócz samej linii i jej infrastruktury, w tym telegrafu i telefonu, towarzystwo organizowało wzdłuż linii szpitale, szkoły, w tym 20 szkół kolejowych, biblioteki, a także zakłady przemysłowe związane z jej budową (tartaki itp.). thumb|left|Urząd Kolei Wschodniochińskich w Harbinie W budowie kolei brali udział polscy inżynierowie, m.in. Stanisław Kierbedź i Seweryn Wachowski. Na centrum administracyjne Kolei i Wschodniochińskiej Strefy Kolejowej obrano Harbin. Tam też znajdowały się główne warsztaty.