A provisional government was set up by the rebels in Kairouan after he departed. Similar incidents unfolded across much of north an interior of the country. At Béja, Téboursouk, Makthar and Jendouba, the governors were forced to flee for their lives and their property was looted. The governor of the Majer tribe in the Thala region was not so fortunate. Besieged in his fortress, he killed dozens of attackers before it fell. He was killed, along with his entire family, and his body decapitated on 21 May. The dead governor's secretary, Ali Ben Ghedhahem (), born in 1814 in Sbeïtla, quickly established himself as the leader of the revolt in the west of the country. When the Bey's soldiers came to his region to collect the mejba, he told people to disobey, and was obliged to flee for safety to the mountains near Oueslatia and Bargou. From here, he began to organise resistance, and soon other tribes began to rally to him. The unorganised revolt of the Mthélith, the Zlass, the Majer and the Fraichiche who camped near the Algerian frontier coalesced into a definite movement as tribal notables came together to swear solemn oaths and began to unite around specific demands—a return to traditional justice and taxation. Ben Ghedhahem's main lieutenants were the Zlassi Seboui Ben Mohamed Seboui and the Riahi Fraj Ben Dahr. Ali Ben Ghedhahem had connections in the Tijaniyyah order of sufis who spread the message of insurrection. From April 1864 onwards, Ali Ben Ghedhahem was referred to as 'the people's Bey' ("bey al-umma"). He decided to lead his forces on Tunis, but only reached as far as El Fahs, where they had a series of inconclusive encounters with forces loyal to the Bey. In April and May 1864 the Bey did not have the military means to strike a decisive blow against Ben Ghedhahem. While seeking to calm the unrest by revoking the constitution of 1861 and announcing that the mejba would not after all be doubled, he therefore prepared his forces and opened clandestine negotiations with Ben Ghedhahem through the Maliki Grand Mufti Ahmed Ben Hussein and the head of the Rahmaniyya sufi order, Mustapha Ben Azouz.