وهو ابن أخي أبي الأعور السلمي صاحب خيل معاوية بصفين فقدم أفريقية سنة ١١٠ في ربيع الأول فدخل القيروان فجأة وذلك يوم الجمعة فألفى خليفة بشر بن صفوان قد تهيأ لشهود الجمعة ولبس ثيابه فقيل له: (هذا عبيدة قد قدم أميرًا) فقال: (لا حول ولا قوة إلا بالله هكذا تقوم الساعة بغتة) وألقى بنفسه فما حملته رجلاه ودخل عبيدة فأخذ عمال بشر وأصحابه فحبسهم وأغرمهم وعذب بعضهم. وفي سنة ١١٠ ولى عبيدة بن عبد الرحمن المذكور عثمان بن أبي نسمة على الأندلس فقدمها في شعبان. وفي سنة ١١١ قدم إلى الأندلس واليًا أيضًا من قبل عبيدة بن عبد الرحمن صاحب أفريقية والمغرب كله حذيفة بن الاحوص القيسي وقيل: الاشجعي وذلك في غرة محرم من السنة المذكورة. وفي سنة ١١٢ ولى عبيدة المذكور على الأندلس أيضًا الهيثم بن عبيد الكناني فقدمها في محرم أيضًا من هذه السنة ثم توفي سنة ١١٤ وكانت ولايته سنتين وأيامًا ولما أخذ عبيدة عمال بشر وأصحابه وأغرمهم وعذبهم كان فيهم أبو الخطار الحسام بن ضرار الكلبي وكان شريفًا في قومه مع صفاحة وبراعة وكان ولي في أفريقية ولايات كبيرة في أيام بشر بن صفوان فعزله عبيدة ونكل به فقال طويل:
أفألم بني مروان فيها دماءنا وفي الله إن لم تنصفوا حكم عدل
كأنكم لم تشهدوا مرج راهط ولم تعلموا من كان ثم له الفضل
تعاميتم عنا بعين جلية وأنتم كذا ما قد علمنا لنا فعل
[ ١ / ٥٠ ]
وبعث بهذه الأبيات إلى الخليفة هشام بن عبد الملك فأمر هشام بعزل عبيدة من أفريقية والمغرب فقفل منه واستخلف عقبة بن قدامة وذلك في شوال سنة ١١٤ فكان ملك عبيدة بأفريقية أربع سنين وستة أشهر وتوجه إلى الشام سنة ١١٤ بهدايا وتحف عظيمة وبقي خليفته على القيروان ستة أشهر. وفي سنة ١١٣ كان عمال أفريقية والأندلس الذين كانوا في السنة قبلها ثم ولي الأندلس عبد الرحمن بن عبد الله الغافقي فغزا الروم واستشهد مع جماعة من عسكره سنة ١١٥ بموضع يعرف ببلاط الشهداء وفيها أصاب الناس مجاعة عظيمة.