Железные дороги в Монголии появились в 1938 году. Строительство Трансмонгольской магистрали началось в 1947 году от станции Наушки (СССР, станция ВСЖД), куда от Улан-Удэ в 1939 году была проложена южная ветка от Транссиба. До этого в Монголии существовали открытая в 1938 году 43-километровая ветка, соединявшая угольные шахты в Налайхе со столицей; и использовавшаяся только для перевозки грузов 236-километровая ветка, соединявшая Борзю (СССР, станция ЗабЖД) с Баян-Туменом (совр. Чойбалсан) на северо-востоке страны (открыта в 1939 году)[1].
Строительство железнодорожной линии от Наушки до Улан-Батора было отложено из-за Второй мировой войны и завершено в ноябре 1949 года. Советский Союз, Монголия и Китайская Народная Республика договорились продлить линию от Улан-Батора до Цзинина в Китае[1].
Регулярное сообщение от Наушек до Улан-Батора началось 23 декабря 1950 года[2], а к китайской границе линия подошла в 1955 году, и с января 1956 года открылось прямое железнодорожное сообщение до Пекина[1].

В 1958 году железная дорога перешла на дизельные двигатели и автоматизировала переключение. В 1963 году были построены ответвления к угольным шахтам в Шарынголе (63 км (39 миль)) и в Баганууре в 1982 году (85 км), медному руднику в Эрдэнэте в 1975 году (164 км), руднику плавикового шпата в Бор-Ондоре в 1987 году (60 км) и нефтеперерабатывающему заводу в Цююнбаяне (63 км )[3].

Модернизация в 1990-х годах заменила некоторые старые локомотивы советского производства более мощными американскими моделями и установила волоконо-оптические кабели вдоль путей для связи и сигнализации.

В 2022 году была открыта линия, соединяющая ответвление в Цююнбаяне с Ханги на китайской границе. Ожидается, что линия восток–запад, соединяющая Цююнбаян с угольными шахтами в Таван Толгой (также соединена с китайской границей в 2022 году), откроется к концу 2023 года[4].