Hajjaj ibn Yousuf, the great Muslim viceroy of Iraq gave the governorship of Khurasan to Qutaiba ibn Muslim in 705. Qutaiba was also instructed to carry the holy war eastwards into the heart of Asia. Qutaiba was soldier and diplomat of outstanding ability. The nucleus of his force was the Arab tribal element which had been removed to this distant frontier from Kufa and Basra, but many recruits were obtained from the native Iranian population, a large number of whom had embraced Islam and were willing to fight under Arab leadership against their hereditary enemies, nomads of Turan.

He made Merv his military headquarters from where he made attacks on Transoxiana, the climate of which was not suitable for Mujahideen's attack round the year. During the severe cold weather Qutaiba was obliged to return to Merv and resume attacks when favourable climatic conditions prevailed. He conquered the cities one after another--Sughd, Bukhara, Samarkand, Shash and Farghana. He also struck on Kashghar, a city of T'ang Empire on the frontier of China. He had reached deep into eastern Turkestan, a land which even Alexander had never seen. The Mujahideen had also not reached much further East to the land of T'ang Emperor than the Muslim forces under the command of Qutaiba less than a century after Hejira.