Turkic peoples began settling in the Tarim Basin in the 7th century. The area was later settled by the Turkic Uyghurs, who founded the Qocho Kingdom there in the 9th century. The historical area of what is modern-day Xinjiang in China consisted of the distinct areas of the Tarim Basin (also known as Altishahr) and Dzungaria. The area was first populated by the Tocharians and the Saka, who were Indo-Europeans and practiced Buddhism. The Tocharian and Saka peoples came under Xiongnu and then Chinese rule during the Han dynasty as the Protectorate of the Western Regions due to wars between the Han dynasty and the Xiongnu. The First Turkic Khaganate conquered this region in 560, and in 603, after a series of civil wars, the First Turkic Khaganate was separated into the Eastern Turkic Khaganate and the Western Turkic Khaganate, with Xinjiang coming under the latter.^{[page needed]} The region then became part of the Tang dynasty as the Protectorate General to Pacify the West after the Tang campaigns against the Western Turks. The Tang dynasty withdrew its control of the region in the Protectorate General to Pacify the West and the Four Garrisons of Anxi after the An Lushan Rebellion, after which the Turkic peoples and the other native inhabitants living in the area gradually converted to Islam following the Muslim conquest of Central Asia.

The Turfan and Tarim Basins were populated by speakers of Tocharian languages and Saka languages. Different historians suggest that either the Sakas or Tokharians made up the Yuezhi people who lived in Xinjiang. During the Han dynasty, the Tocharians and Sakas of Xinjiang came under a Chinese protectorate in 60 BC, with the Chinese protecting the Tocharian and Saka city states from the nomadic Xiongnu who were based in Mongolia.

In the 6th through 8th centuries, the region was subject several incursions from the Xiongnu, Muslims, Göktürks, Tibetans, and Turkic nomads. Arab sources claim that first recorded incursion into the Tarim Basin by an Islamic force is the alleged attack on Kashgar by Qutayba ibn Muslim in 715 but some modern historians entirely dismiss this claim. The Tang dynasty defeated an Umayyad coalition at the Battle of Aksu (717). The Umayyad commander Al-Yashkuri and his army fled to Tashkent after they were defeated. The Chinese however were later defeated by the Abbasid Arabs in the Battle of Talas (751).

Tang China lost control of Xinjiang after it was forced to withdraw its garrisons during the An Lushan Rebellion.^{[citation needed]} During the rebellion China received aid from the Uyghur Khaganate in crushing An Lushan's rebels, however, multiple provocations by the Uyghurs such as selling bad quality horses to China, practicing usury when lending to Chinese, and sheltering Uyghurs who committed murder resulted in a major deterioration in relations between China and the Uyghur Khaganate. Tang China then allied with the Yenisei Kirghiz and defeated and destroyed the Uyghur Khaganate in a war, triggering the collapse of the Uyghur Khaganate which caused Uyghurs to migrate from their original lands in Mongolia southwestwards into Xinjiang.^{[citation needed]}

Protected by the Taklamakan Desert from steppe nomads, elements of Tocharian culture survived until the 7th century, when the arrival of Turkic immigrants from the collapsing Uyghur Khaganate of modern-day Mongolia began to absorb the Tocharians to form the modern-day Uyghur ethnic group.

By the 10th century, the area was ruled by the Kingdom of Khotan and Shule Kingdom when the first Turkic began migrating into the area. The Saka Kings were still culturally-influenced by the Buddhist homeland of Northern India, with their rulers adopting Sanskrit names and titles.^{[citation needed]} The rulers of Khotan grew anxious of hostilities with Turkish khanates, as evidenced by the Mogao grottoes, were they commissioned painting number of divine figures along with themselves. By the time the Uyghurs and the Kara-Khanids invaded, Khotan was the only state in the area that had not come under Turkic rule.

The Kara-Khanids formed from several Turkic groups that had increasingly settled portions of the Kashgar area. The tribes are thought to have converted to Islam following the conversion of Sultan Satuq Bughra Khan in 934. Khotan conquered Kashgar in 970, after which a long war ensued between Khotan and the Kara-Khanids. The Karakhanids fought Khotan until sometime before 1006 when the Kingdom was conquered by Yusuf Qadir Khan. The attacks likely related to Khotanese requests for aid when China. Relations with China factored heavily in the war. In 970, after the Khotanese capture of Kashgar, an elephant was sent as tribute by Khotan to Song dynasty China. After the Qara Khanid Turkic Muslims defeated the Khotanese under Yusuf Qadir Khan at or before 1006, China received a tribute mission in 1009 from the Muslims.

Following the war, a Buddhist revival occurred in the Tangut Empire, located in contemporary Western Xia, following the attacks on the Buddhist states in the region. The Empire became a safe haven for Indian Buddhist monks who were attacked and forced to flee to Tangut.