وكان الأمير عبيد الله بن الحبحاب قد جهز حبيب بن أبي عبيدة بن عقبة الفهري غازيا إلى جزيرة صقلية فقدم معه ولده عبد الرحمن على طلائعه وكان عبد الرحمن أحد الأبطال فلم يثبت له أحد وظفر ظفرا ما سمع بمثله قط وسار حتى نزل على أكبر مدائن صقلية وهي مدينة سرقوسة فقابلوه فهزمهم وهابته النصارى وذلوا لأداء الجزية.
وكان والده عبيد الله بن الحبحاب قد استعمل على طنجة وما يليها عمر بن عبد الله المرادي فظلم وعسف وأساء السيرة في البربر فثاروا واغتنموا غيبة العساكر وتداعت على عمر القبائل وعظم الشر. وهذه أول فتنة كانت بالمغرب بعد تمهيد البلاد فأمرت البربر عليهم ميسرة الحقير فأسرع حبيب الفهري الكرة من صقلية فالتقى هو وميسرة فكانت ملحمة هائلة فاستظهر ميسرة.
ثم إن البرب أنكرت سوء سيرة ميسرة وتغيروا عليه فقتلوه وأمروا عليهم خالد ابن حميدة الزناتي فأقبل بهم في جيش عظيم فكانت بينهم وبين عسكر الإسلام ملحمة مشهورة قتل فيها خالد الزناتي وسائر من معه وذهب فيها خلق من فرسان العرب ولهذا سميت غزوة الأشراف.
ومرج أمر الناس وقويت الخوارج. وعمد الناس إلى عبيد الله بن الحبحاب فعزلوه فغضب الخليفة هشام لما بلغه وتنمر، وبعث على المغرب كلثوم بن عياض القشيري.