Balj was a member of the Banu Qushayr, a branch of the Hawazin tribe, and was the nephew of Kulthum ibn Iyad al-Qasi, who had been appointed governor of Ifriqiya by the Umayyad caliph Hisham.
Problems began when billeting Umayyad troops and requisitioning supplies from their Arabian-Ifriqiyan hosts, under their commander Habib ibn Abi Obeida al-Fihri.
Ancient pre-Islamic tribal rivalries persisted between the largely Kalbid - Qahtanite (Yemenite) Ifriqiyan and Andalusian Arabs, and the north Arabian Qaysid - Mudharite' (Hijazi-Nejdi) tribes that comprised the Arabian-Syrian junds.
Reportedly one Arab merchant who was caught having surreptitiously sent two grain boats to the starving Syrians was publicly tortured and executed on the governor's command.
Crossing the straits of Gibraltar in early 742, the Syrians assisted in the swift defeat of the three main Berber rebel armies through a series of encounters – at Medina-Sidonia, Córdoba and finally Toledo.