وهو ابن أخي أبي الأعور السلمي صاحب خيل معاوية بصفين فقدم أفريقية سنة 110 في ربيع الأول فدخل القيروان فجأة وذلك يوم الجمعة فألفى خليفة بشر بن صفوان قد تهيأ لشهود الجمعة ولبس ثيابه فقيل له: (هذا عبيدة قد قدم أميرًا) فقال: (لا حول ولا قوة إلا بالله هكذا تقوم الساعة بغتة) وألقى بنفسه فما حملته رجلاه ودخل عبيدة فأخذ عمال بشر وأصحابه فحبسهم وأغرمهم وعذب بعضهم. وفي سنة 110 ولى عبيدة بن عبد الرحمن المذكور عثمان بن أبي نسمة على الأندلس فقدمها في شعبان. وفي سنة 111 قدم إلى الأندلس واليًا أيضًا من قبل عبيدة بن عبد الرحمن صاحب أفريقية والمغرب كله حذيفة بن الاحوص القيسي وقيل: الاشجعي وذلك في غرة محرم من السنة المذكورة. وفي سنة 112 ولى عبيدة المذكور على الأندلس أيضًا الهيثم بن عبيد الكناني فقدمها في محرم أيضًا من هذه السنة ثم توفي سنة 114 وكانت ولايته سنتين وأيامًا ولما أخذ عبيدة عمال بشر وأصحابه وأغرمهم وعذبهم كان فيهم أبو الخطار الحسام بن ضرار الكلبي وكان شريفًا في قومه مع صفاحة وبراعة وكان ولي في أفريقية ولايات كبيرة في أيام بشر بن صفوان فعزله عبيدة ونكل به فقال طويل:

أفألم بني مروان فيها دماءنا ... وفي الله إن لم تنصفوا حكم عدل

كأنكم لم تشهدوا مرج راهط ... ولم تعلموا من كان ثم له الفضل

تعاميتم عنا بعين جلية ... وأنتم كذا ما قد علمنا لنا فعل