В условиях всеобщего брожения умов берберы выжидали благоприятной возможности, чтобы взять в руки оружие, когда в 740 году Обайдаллах отправил большую часть своих войск на Сицилию. Когда эти войска погрузились на корабли, стало очевидно, что восстание может начаться в любой момент – нужен только самый пустяковый повод. Однако правитель Тингитаны неблагоразумно выбрал именно этот момент, чтобы применить кайситскую систему и приказать местным берберам выплатить двойную дань, как если бы они не были мусульманами. Они сразу же взялись за оружие, обрили головы, привязали свитки Корана к наконечникам копий, как хариджиты, и поручили командование Майсаре, самому рьяному из сектантов, который был одновременно священнослужителем, солдатом и демагогом. Они напали на Танжер, захватили его и казнили правителя и всех арабов, которых сумели отыскать. При этом они применяли свои доктрины с такой бесчеловечной жестокостью, что не щадили даже маленьких детей. Из Танжера Майсара повел своих людей в провинцию Сус, которой тогда правил Исмаил, сын Обайдаллаха. Не дожидаясь их появления, берберы собрались толпой и убили правителя. Арабы тщетно пытались сопротивляться, но, потерпев поражение на всех фронтах, были вынуждены покинуть страну. Через несколько дней весь запад Африки, на покорение которого арабам потребовалось так много лет, был для них потерян. Берберы организовали выборы халифа. Революционный дух оказался настолько демократичным, что выбор народа пал не на знатного человека, а на храброго Майсару, ранее бывшего водоносом на рынке Кайруана.
Застигнутый врасплох, Обайдаллах приказал Окбе, правителю Испании, высадиться на побережье Тингитаны. Окба послушно направил туда войска, но они потерпели поражение. После этого он лично погрузился на корабли с более крупными силами, высадился на африканском побережье и предал мечу каждого бербера, который попался ему на пути. Но подавить восстание ему не удалось.
Обайдаллах, давая инструкции Окбе, одновременно направил приказ фихриту Хабибу, главе сицилийской экспедиции, чтобы тот как можно скорее вернулся в Африку с войсками, а испанский флот пока будет сдерживать сицилийцев. Однако опасность нарастала – восстание распространялось со скоростью лесного пожала – и Обайдаллах посчитал неблагоразумным ожидать возвращения армии с Сицилии. Собрав все доступные войска, он отдал их под командование фихриту Халиду, обещав усилить их людьми Хабиба, как только они вернутся. Халид выступил, встретил Майсару у Танжера и дал ему бой. После упорного, но ничего не решившего сражения Майсара отступил в Танжер, где был убит собственными солдатами: привыкнув к победам, они или не смогли смириться с поражением, или после возвышения этот демагог предстал предателем демократических принципов. Арабские хронисты склонялись к последней причине, и в этом случае берберы действовали в рамках своих прав и исполняли свой долг. Ведь их доктрины предписывали сместить или даже убить халифа, отступившего от принципов веры.
Берберы, избрав нового лидера, снова перешли в наступление, на этот раз с большим успехом: в разгар последовавшего сражения отряд, которым командовал преемник Майсары, ударил в тыл арабам, и те, осознав опасность окружения, в беспорядке бежали. Но Халид и приближенная к нему знать были слишком горды, чтобы пережить позор такого поражения, и они бросились на врага, решив дорого продать свои жизни. Все они погибли. Это роковое сражение, в котором пал цвет арабского рыцарства, получило название Битва аристократов.
Хабиб вернулся с Сицилии и выступил в окрестности Тагорта, но, услышав о разгроме Халида, не рискнул нападать на берберов. Вскоре Африка стала напоминать корабль, дрейфующий без руля и ветрил. Обайдаллаха сместили сами арабы, обвинившие его, и не без оснований, в том, что именно он навлек на них все эти несчастья. Халиф Хишам дрожал от ярости и горя, когда услышал о берберском восстании и разгроме своей армии. «Клянусь Аллахом! – заявил он. – Я покажу им, что такое гнев араба старой закалки! Я вышлю против них армию, какой они никогда не видели. Ее авангард нападет на них, когда арьергард еще будет в Дамаске!» Четыре региона Сирии получили приказы направить в армию по шесть тысяч солдат. Пятый, Киннисрин, – три тысячи. Эти двадцать семь тысяч человек должны были соединиться с трехтысячной египетской армией и всеми африканскими силами. Хишам поручил командование армией, а также управление Африкой, опытному кайситу из племени кошайр по имени Кульсум. В случае смерти Кульсума его должен был сменить его племянник Балдж, а если умрет и Балдж, командование должен был взять на себя Салаба – йеменит из племени Амила и лидер армии Иордана. Исполненный решимости примерно наказать мятежников – чтобы другим неповадно было, – халиф разрешил военачальнику обезглавливать всех, кто попадет ему в руки, и грабить все поселения на его пути.