Qutayba ibn Muslim was born in 669 CE in Basra, where his family was influential.

His father, Muslim ibn ʿAmr, had enjoyed the favor of the Umayyads, and fell at the Battle of Maskin at the close of the Second Islamic Civil War.

Qutayba had risen at first as the protégé of Anbasa ibn Sa'id, but had been noticed by the powerful governor of Iraq and the East, al-Hajjaj ibn Yusuf, during the suppression of the revolt of Abd al-Rahman ibn Muhammad ibn al-Ash'ath in 700/701.

Under al-Hajjaj's patronage, he had taken Rayy from the rebel Umar ibn Abi'l-Salt in 701, and became the city's governor.

Caliph Abd al-Malik ibn Marwan appoints Qutayba as governor of Khurasan in late 704 or early 705.

The choice of Qutayba, who hails from the relatively weak Bahila tribe, is intended by al-Hajjaj to heal the destructive feud between the South Arab or "Yemeni" (Azd and Rabi'ah) and North Arab (Qaysi) tribal confederations in Khurasan by providing a governor who belongs to neither faction.

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

Furthermore, as Qutayba lacks a strong tribal base of his own, he could be expected to remain firmly attached to his patron.

Qutayba will spend the next ten years of his life in Central Asia, consolidating and expanding Muslim rule there.

In this endeavor, both his military and diplomatic and organizational abilities stand him in good stead; most importantly, he is able to enlist the support of the local Iranian population and the powerful dihqan (the Iranian "gentry") class.

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

The first Arab attacks across the Oxus had ranged as far as Shash (Tashkent) and Khwarizm, but they had been little more than raids aiming at seizing booty and extracting tribute, and had been interrupted by the intertribal warfare that had broken out in Khurasan during the Second Islamic Civil War (683–692).

Subsequent governors, most notably Sa'id ibn Uthman and al-Muhallab ibn Abi Suffrah, had made attempts to conquer territory across the river, but they had failed.

The native princes, for their part, have tried to exploit the Arabs' rivalries, and with the aid of the Arab renegade Musa ibn Abdallah ibn Khazim, who in 689 seized the fortress of Tirmidh for his own domain, they managed to eject the Arabs from their holdings.

Nevertheless, the Transoxianian princes remain riven by their own feuds, and fail to unite in the face of the Arab conquest, a fact that Qutayba will suitably exploit after 705.