Archaeological evidence shows that Tuva was inhabited in the Paleolithic era by heterogeneous tribes of Europoid, Mongoloid, and mixed stock. In addition to native tribes, Scythians (or at least their culture) were present in Tuva (seventh to third centuries B.C. ), followed by the Huns (second century B.C. to second century A.D. ) and Ancient Turks (sixth to twelfth centuries)—most notably the Uighurs (eighth century) and the Kyrgyz (ninth century), whose ethnonyms survive today as clan names in western and southeastern Tuva, respectively. There are notable burial sites from each of these historical periods that have yielded rich archaeological material: Arzhan (Scythian), Kökel (Hunnic), Tere-Khöl (Uighur), and various locations with "stone men" (Tuvan: közhee ; Russian: balbal ) with runelike inscriptions in Ancient Turkic (Kyrgyz).
In 1207 Tuva was conquered by armies of Chinggis (Genghis) Khan. It was settled over the following centuries by Mongolian tribes, who eventually became absorbed by the local Turkic, Ket, and Samoyed population, under the rule of the Altyn khans. From 1757 to 1911 the territory was ruled by the Ch'ing dynasty. In 1914 Tuva, without being given a choice in the matter, was placed under the protection of Russia.
In the years following the October Revolution of 1917, several battles between the Reds and the Whites took place in Tuva. The name of Tuva's capital reflects that struggle: originally Khem Beldiri (Tuvan for "River Confluence"), it was renamed Byelotsarsk in 1914 (Russian for "White Czar"), and Kyzyl-Khoto (Tuvan for "red" and Mongolian for "town") in 1921. Today it is known simply as Kyzyl.
From August 1921 to October 1944 Tuva was a nominally independent state issuing its own currency and postage stamps. (Virtually all the stamps were designed by Russians and printed in Moscow, however.) Although only the USSR and Mongolia sent diplomatic representatives to Kyzyl, the maps of many other countries showed Tuva as a separate state. The government of Taiwan still considers Tuva Chinese territory. Near the end of World War II the "small khural " (politburo) of Tuva, led by Salchak Toka, a graduate of the Communist University of the Toilers of the East (acronym KUTV in Russian), petitioned that Tuva be brought into the USSR.