To increase his strained manpower, Qutayba initiated the wide-scale levy of native Khurasani and Transoxianian soldiers who fought alongside the Arab Muslim troops.

The Bahila were neutral between the two groups, but generally allied themselves to the Qays, thus furthering al-Hajjaj's policy of emasculating Azdi power, which had been dominant in Khurasan during the governorship of al-Mufaddal's brother, Yazid ibn al-Muhallab.

[1][8] The Arabs had reached Central Asia in the decade after their decisive victory in the Battle of Nihavend in 642, when they completed their conquest of the former Sassanid Empire by seizing Sistan and Khurasan.

[9] The first Arab attacks across the Oxus ranged as far as Shash (Tashkent) and Khwarizm, but they were little more than raids aiming at seizing booty and extracting tribute, and were interrupted by the intertribal warfare that broke out in Khurasan during the Second Fitna (683–692).

[1][15][16] After extensive negotiations led by Sulaym the Persian, the tarkhan Nizak, ruler of the Hephthalite principality of Badghis, surrendered to Qutayba, and pledged to accompany him in his expeditions.

The men of fighting age were executed, the women and children sold off as slaves, and enormous booty amassed, especially in armour and weapons, which equipped the Arab army.

Qutayba avoided a battle, and engaged in negotiations to gain time, before executing a rapid retreat to safety through the Iron Gate to beyond the Oxus, crossing the river at Tirmidh.

[22][24] For 709, al-Hajjaj drew up a new plan for his subordinate: the Arabs launched a direct attack on Bukhara, which caught the Sogdian alliance—possibly weakened by the death of its leader, the Wardan Khudah—by surprise.

This move proved effective in discouraging the rebellion of more local princes, and in spring 710, Abd al-Rahman was able to re-establish Muslim control over Tokharistan almost without bloodshed.

Most of the rebel rulers fled or capitulated, and finally, Nizak was captured with the assistance of some native princes and executed on al-Hajjaj's orders, despite promises of pardon.

Lower Tokharistan was more firmly incorporated into the Caliphate, as Arab district representatives were appointed alongside the local princes, who were gradually relegated to secondary positions.

[29][30] From this point on, Balkh began developing "as a centre of Arab power and Islamic culture", in the words of C. E. Bosworth; within a generation, it was Islamicized to the extent of briefly replacing Marw as the provincial capital of Khurasan.

Later, in 712/13, Qutayba built a mosque in the city's citadel, but although the Arab authorities encouraged the conversion of the native population by paying them to attend prayers, Islamization proceeded slowly.

[1][32][33] At the same time, Qutayba had adopted a measure that marked a radical departure from previous practice in the East and had long-term repercussions: the raising of native Khurasani auxiliary levies, usually some ten to twenty thousand strong and mostly composed of non-converts, to supplement the Arab tribal army, the muqatila.

[34][35] Gibb suggests that this move may be seen as an answer to the need for more troops to control the conquered territories and continue Muslim expansion, as well as a means of placing the local manpower in Arab service and depleting it at the same time, reducing the risk of anti-Arab revolts.

[38] Later in 711, al-Hajjaj ordered Qutayba to march against the Hephthalite kingdom of Zabulistan, whose rulers, referred to by their title, Zunbil, had long remained an indomitable thorn in the Arabs' side and menaced their province of Sistan.

[40][41][42] Qutayba's victories, parallel with the conquests of Muhammad ibn al-Qasim in northwestern India, awoke such enthusiasm and hopes among the Muslims that al-Hajjaj is reputed to have offered the governorship of China to whoever of the two first reached it.

[43] Byzantine Empire Sassanid Persia Caucasus Other regions Taking advantage of Qutayba's absence in the south, the inhabitants of Samarkand overthrew their ruler Tarkhun due to his passive stance towards the Arabs, and installed the prince Ghurak in his stead.

[46] The Khwarizmshah, whose name is given as Jigan or Chigan by Bal'ami, faced a rebellion by his younger brother Khurrazadh and a powerful rival, the king of Khamjird, and asked Qutayba for help, offering recognition of the Caliphate's suzerainty, money, livestock and the payment of tribute in exchange.

The local Afrighid dynasty was left in place, with Askajamuk II, the son of Azkajwar II, as the new Khwarizmshah, but the conquest of Khwarizm was accompanied by great brutality: the 11th-century Khwarizmian scholar al-Biruni compares the events with a barbarian sack, as the Arabs proceeded to massacre most of the upper classes who had fomented the revolt, and destroyed a great many objects of Khwarizmian culture, including manuscripts.

The Sogdians had disbanded most of their forces, and the Arabs, reinforced with levies from Bukhara and Khwarizm, were able to brush aside the local resistance and advance straight to the city itself and lay siege to it.

[24][51] Qutayba initially granted surprisingly lenient terms: the payment of an annual tribute and the provision of an auxiliary corps as with Bukhara and Khwarizm, as well as the construction of a mosque inside the city and the celebration of prayers there by the Arab army.

His only concern was that his old rival, Yazid ibn al-Muhallab, might be restored to the Caliph's favour after al-Hajjaj's death, and he took few precautions except for removing his family and belongings from Merv to Shash and placing a guard on the Oxus.

[59][60] His campaign against Ferghana was under way when news reached the army of Caliph Walid's death and the accession of his brother Sulayman ibn Abd al-Malik to the throne.

[52][74] ^ a: According to the historian al-Tabari, the regular Muslim forces in the region mustered 47,000 Arabs (9,000 from Basra, 7,000 Bakr, 10,000 Tamim, 4,000 Qays, 10,000 Azd and 7,000 Kufans) and 7,000 mawali or native converts.