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