Created by Arab tribes in Palestine, headed by Mufraj bin Dagfal al-Jarrah Taiy, al-Hakim had to face another rebellion hatched in 397/1004, which lasted for about three years. This was the rebellion of the tribe of Banu Jarrah, a part of the Yameni tribe, called Taiy, who had settled in southern parts of Palestine in the Balqa region. Unlike the revolt of Abu Raqwa, Mufraj's rising was not influenced by religious teaching, nor was it a serious threat to the Fatimids. He began to plunder the pilgrims, and planned to occupy Palestine to establish his family rule. In 400/1009, al-Hakim appointed his general Yarkhtagin to Aleppo to suppress the rebellions, but Mufraj intercepted him at Askalan and raided. Mufraj sacked his materials and captured him. The rebels also occupied Ramla.
Mufraj went to Hijaz and swore allegiance to Hasan bin Jafar (d. 430/1038), surnamed Abul Fatuh as an amir, and brought him to Ramla. Thus, Mufraj dominated both in Palestine and Hijaz, and started coinage in the name of Abul Fatuh. Al-Hakim was much alarmed by these events in his state and tried to suppress the rebellion before it assumed serious proportions. He wrote a letter of remonstration to Mufraj and offered him a sum of 50,000 dinars in return for the safety of Yarkhtagin. Al-Hakim also threated him with severe consequences if he harmed his general. Soon afterwards, the Fatimid general Yarkhtagin had been executed.
To discredit Abul Fatuh in Mecca and regain Hijaz, al-Hakim communicated with another in Mecca, known as Ibn Abu Tayyib and helped him, resulting re-occupation of Hijaz by the Fatimid. Al-Hakim wrote to Mufraj, promising him estates and other gifts if he would cease from rebellion. Mufraj resolved to abandon Abul Fatuh, who returned to Hijaz. Meanwhile, Mufraj accepted the offer of al-Hakim and took his money. He however retained his mastery over Palestine and continued to menace the peace and security. The pilgrims from Egypt could no longer travel to Hijaz to perform hajj as their caravans were used to be sacked.
At length, al-Hakim was impelled to take field against Mufraj. In 404/1013, he sent 20,000 horsemen under Ali bin Falah, whom he invested the title qutb ad-dawla (magnate of the state), and ordered the chief of Damascus to join the campaign. Meanwhile, Mufraj died and his supporters scattered. Ali bin Falah captured Ramla and restored law and order.