Throughout his early military career, he participated in the Arab campaigns against the Persians in Fars, Ahwaz, Sistan and Khurasan during the successive reigns of caliphs Umar (r. 634–644), Uthman (r. 644–656), Ali (r. 656–661) and Mu'awiya I (r. 661–680).

Following the collapse of Umayyad rule in Iraq and Khurasan in 683–684, during the Second Muslim Civil War, al-Muhallab was pressed by the Basran troops to lead the campaign against the Azariqa, a Kharijite faction which had taken over Ahwaz and threatened Basra.

He was rewarded with the governorship of that province by the anti-Umayyad caliph Abd Allah ibn al-Zubayr (r. 683–692), whose suzerainty had been recognized in Basra in the wake of the Umayyads' ouster.

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.

[1] 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.

[5] Al-Muhallab was unable to take up his assignment in Khurasan due to the opposition of the Basran troops, who pressed him to lead the campaign against the Azariqa, a Kharijite faction that threatened the city.

[10] After al-Muhallab refused their initial entreaties, the Basran nobles forged a letter from Ibn al-Zubayr calling on him to abandon his assignment to Khurasan and confront the Kharijites instead, which he accepted after securing assurances of loyalty from the troops and sufficient funds from the provincial treasury.

[1] With the key backing of the local mawali, al-Mukhtar had recently suppressed a rebellion by Kufa's Arab nobility, prompting thousands of them to seek refuge and support from Mus'ab in Basra.

One of the leading Kufan nobles, Muhammad ibn al-Ash'ath, pressed Mus'ab to march against al-Mukhtar, but the former refused unless al-Muhallab agreed to join.

[9] In 690, eight months after he was reassigned to the war against the Azariqa, Mus'ab was defeated and killed by the Umayyad army led by Caliph Abd al-Malik ibn Marwan at the Battle of Maskin.

[22] Abd al-Malik's kinsman and governor over Basra, Khalid ibn Abdallah, relieved al-Muhallab of command and assigned him to collect the kharaj (land tax) of Ahwaz.

[24] Afterward, in 693/94, Abd al-Malik directly appointed al-Muhallab commander of the war against the Azariqa, but later that year, his troops deserted the field against them at Ramhormoz following news of the death of Bishr ibn Marwan, Khalid's replacement as governor of Basra.

[1] Toward the end of 694, Abd al-Malik appointed al-Hajjaj ibn Yusuf governor over Iraq (Kufa and Basra) and the latter strongly backed al-Muhallab's campaign.

[9] During this time, he is credited with introducing iron stirrups on the saddles of his army's war horses,[25] in place of the wooden ones, which could barely withstand a rider's weight.

According to the historian Muhammad Abdulhayy Shaban, al-Hajjaj viewed the unruly Tamim's dominance as the major impediment to his policies of centralization and expansion in the eastern half of the Caliphate.

[25] Al-Muhallab began his term in 698 by preparing an army in the provincial capital of Merv, composed of his men from the campaigns against the Azariqa, Khurasani troops and local forces commanded by the mawali brothers Thabit and Hurayth ibn Qutba.

While the traditional Muslim sources generally attribute his withdrawal to heartbreak over al-Mughira's death, al-Mada'ini notes that a conspiracy by troops of the Mudar (the alliance of the Tamim and Qays factions of the Basran and Khurasani armies) in his camp prompted him to abandon the war effort.

[31] Ibn al-Ash'ath's forces swept westward through Fars and at one point gained control of Kufa and Basra before being stamped out by al-Hajjaj and his Syrian troops in 701.

[31] The historian Hugh Kennedy describes al-Muhallab as "a figure of almost legendary prowess on the battlefield and a man with a great reputation as a commander", which he gained in "hard, unrewarding campaigning" against the Azariqa in the unfavorable terrain of Fars and Ahwaz.

[25] According to Julius Wellhausen, though al-Muhallab's career in Khurasan "did not add to his renown in war", it brought about a development of "great importance" in the province: the influx of the Azd.

Together with their allies from the Rabi'a, they counted 21,000 soldiers out of the 40,000-strong Arab army of Khurasan, and ended the previous dominance of the Tamim–Mudar alliance; a balance of power was thenceforth established, tilted only by support from the governor to either side.

[34] The descendants of al-Muhallab and his father Abu Sufra, known as the Muhallabids, became a prominent family, "famed for their numbers and their remarkable role in early Islamic history" according to Crone.