Mongolia's capital spent more than a century on the move. Its current name, "Red Hero," was added only in 1924, and partly at an outsider's insistence.
The city began in 1639 as Örgöö, which literally means "palace." It was a yurt monastery, built as the seat of the Buddhist leader Zanabazar, the first Jebtsundamba Khutughtu. A monastery of tents could be packed up, and it was. It moved 29 times before settling in 1778 near the Tuul River, beneath the mountain Bogd Khan Uul.
The names moved with it. By 1651 it was Nomiin Khüree, "Khüree of Wisdom." By 1706 it was Ikh Khüree, "Great Khüree." Chinese speakers called it Da Kulun. Russians took the old name Örgöö and made it Urga, and in the West the city was generally known as Urga until 1924. Britannica notes that the city developed as a trade centre between China and Russia.
In 1911 Mongolia declared independence, and the city became Niislel Khüree, "Capital Khüree."
The change to "Red Hero" came with the communist state. In 1924 the city became the capital of the new Mongolian People's Republic. Wikipedia dates the renaming to 29 October 1924. According to its account, delegates first voted for Bator-khoto, "City of the Hero." The Comintern representative, the Soviet Kazakh official T. R. Ryskulov, insisted on something more revolutionary. The result was Ulan Bator Khoto: the red hero's city.
Who is the hero? The popular answer is Damdin Sükhbaatar, commander of the partisan army in the 1921 revolution. He fought Chinese occupying troops and White Russian forces. He died on 20 February 1923, the year before the renaming. His own name means "Axe Hero," and baatar is the word the two names share. But the link is less firm than it sounds. Wikipedia's article on the city says it was named "possibly" in his honor. Its article on Sükhbaatar presents the honor as fact, so the sources do not agree.
Outsiders learned the Russian spelling, Ulan-Bator. Ulaanbaatar follows the Mongolian spelling more closely, and it is now the usual form in English.
The hero word itself may be widely traveled. The Russian bogatyr, a hero of epic folk tales, is thought by some scholars to come from a related Turco-Mongol word for a brave warrior. That origin is one of several proposed.