Al-Muhallab was born in . Most sources hold that his father, Abu Sufra, was an Arab from the
Azd tribe, with 9th-century historian
al-Baladhuri asserting that he belonged to one of the tribe's noble households, the Atik of the
Dibba coast. However, according to another 9th-century scholar,
Abu Ubayda, Abu Sufra was a
Persian weaver who migrated from the Persian Gulf island of
Kharak to
Oman before settling in the Arab garrison town of
Basra in Iraq. According to this account, he was accepted by the Azd as one of their own by dint of the courage he demonstrated in battle. The Azd had dominated Oman (Uman) since the
pre-Islamic era and hence were known as the "Azd Uman" to distinguish them from the "Azd Sarat", who were based in western Arabia. Al-Muhallab and his father were initially settled among the Azd Uman at the Arab military settlement of
Tawwaj in
Fars. This likely marked the start of al-Muhallab's military career. During the reign of Caliph
Umar () al-Muhallab participated in operations against the Persians in
Ahwaz. He later fought them in
Sistan in 653/54, during the reign of Caliph
Uthman (). In 656, during the reign of Caliph
Ali (), al-Muhallab and his father were moved to Basra. Though in the reports cited by 9th-century historians
al-Tabari and al-Awtabi, Ali declared Abu Sufra the chief of Azd, the modern historian
Patricia Crone holds that "neither Abu Sufra nor al-Muhallab ever held" the chieftainship of the Basran Azd. Rather, they gained prestige and power through their military prowess not their tribal status. At some point during Ali's caliphate, al-Muhallab fought again in Ahwaz. Between 662 and 665, during the reign of the
Umayyad caliph
Mu'awiya I (), al-Muhallab led a renewed campaign into Sistan, reaching as far as
Sindh. In 664, he attacked
Banna ( present day
Bannu, Pakistan) and al-Ahwar
Lahor (Swabi), but was countered by local forces. There, he adopted the Indian tradition of trimming the tails of his war horses. After his Sistan campaign, he was transferred, for an unspecified period, to
Khurasan front in 670, fighting under the command of
al-Hakam ibn Amr al-Ghifari. He returned to this front under the governor of Khurasan,
Sa'id ibn Uthman, in 676 and then again in 681, in the company of other reputable Basran generals recruited by the newly appointed governor,
Salm ibn Ziyad. This time he remained in the province for a further three years, after which Umayyad authority collapsed in Khurasan and most of the Caliphate. Salm consequently left the province, initially appointing al-Muhallab as his deputy governor, but the latter was quickly edged out by
Abd Allah ibn Khazim al-Sulami. The latter had the backing of the
Banu Tamim, a powerful tribal faction in the Khurasan army, while al-Muhallab lacked tribal support as the Azd presence in the province was negligible at the time. Iraq, and Khurasan with it, ultimately came under the suzerainty of the anti-Umayyad,
Mecca-based caliph,
Abd Allah ibn al-Zubayr (), who appointed al-Muhallab governor of Khurasan. Meanwhile, a mass wave of Azdi tribesmen from Oman had migrated to Basra between 679 and 680, merged with the Azd Sarat already present in the city and formed a strong alliance with the
Rabi'a tribal confederation, a major faction in the Basran garrison. After Yazid's governor in the city,
Ubayd Allah ibn Ziyad, was ousted in the aftermath of the caliph's death, the Azdi leader of the Azd–Rabi'a alliance, attempted to gain control of the city and was killed by members of the rival Banu Tamim, the other major faction of the Basran garrison. This precipitated hostilities between the two groups, which spread to Khurasan where troops from both factions were deployed. ==First campaign against the Kharijites==