[1] Al-Hajjaj considered appointing him lieutenant governor of Khurasan, but was dissuaded by Caliph Abd al-Malik and ultimately selected Qutayba ibn Muslim.
[3][4] Under Caliph Abd al-Malik (685–705), the viceroy of Iraq, al-Hajjaj ibn Yusuf, set about restoring and expanding Umayyad rule across the entire Persian Gulf, including Oman.
[3][5] Al-Hajjaj's initial attempts were repulsed and a large expeditionary force was dispatched under Mujja'a's brother al-Qasim.
[6] Mujja'a was equipped with a 40,000-strong army consisting of troops from the Mudar and Azd tribal factions of Basra garrison.
[9] The combined pressure of al-Hajjaj's generals compelled the Julandid brothers into fleeing for the Zanj coast (Horn of Africa) and Mujja'a and Abd al-Rahman subjected Oman to Umayyad rule.