Przed wybudowaniem Kolei Transmongolskiej istniała linia Ułan Bator – Nalajch (otwarta 11 lipca 1938), która łączy stolicę kraju z kopalniami węgla kamiennego w Nalajchu.

Budowa Kolei Transmongolskiej rozpoczęła się w 1949, a koniec budowy linii oraz jej odgałęzień przypadł na 1961.

1949 – podpisanie umowy między rządami Mongolii i ZSRR w sprawie utworzenia spółki akcyjnej "Ułan Bator Kolej" 1949 – przejazd pierwszego pociągu 1950 – linia osiąga Ułan Bator od strony północnej 1952 – podpisanie trójstronnego porozumienia między rządami Mongolii, ZSRR i Chin, mającego na celu uruchomienie bezpośredniego połączenia kolejowego między ZSRR a Chinami przez Mongolię. 1955 – osiągnięcie granicy mongolsko-chińskiej 1956 – otwarcie bezpośrednich połączeń kolejowych między ZSRR a Chinami przez Mongolię 1956 – otwarcie linii kolejowej Bajantumen (do miasta Czojbalsan) w północno-wschodniej części Mongolii, nie wchodzącej w skład Kolei Transmongolskiej. 1958 – publikacja pierwszego wydania gazety kolejowej 1975 – pierwszy pociąg pasażerski relacji Ułan Bator – Moskwa