مملكة الأوراس وقع في غُضون الحملات العسكريَّة الإسلاميَّة على فُلول الروم تبدلٌ مُذهلٌ في موقف البربر، إذ انفجرت قبائلُ الأوراس بِقيادة ملكتهم التي بايعوها سنة 690م وعُرفت في المصادر العربيَّة والإسلاميَّة باسم «الكاهنة» وكانت خبيرةً بالسحر والتنبؤ بما يقع من الأحداث، واسمها الحقيقي هو «ديهيا بنت ماتية بن تيفان الجرواتيَّة الزناتيَّة»، أي أنها تنحدر من قبيلة جِراوة الزناتيَّة البتريَّة، وقد دانت، على ما يبدو، بالعقيدة اليهوديَّة. وقد حُرِّف اسمها بالعربيَّة فصار «داهية»، ويُحتمل أن يكون مُجرَّد لقب أطلقهُ المُؤرخون اللاحقون عليها لاتصافها بالدهاء، وهذه صفةٌ أساسيَّةٌ عند السحرة والمُشعوذين. ونجحت الكاهنة في تحقيق التفافٍ واسعٍ حول ثورتها من البربر الأوراس ومن بقايا البيزنطيين، فسارت إلى مدينة باغاية الساحليَّة آخر المعاقل المُهمَّة التي احتفظ بها البيزنطيُّون وسيطرت عليها، ثُمَّ راحت تتحدى المُسلمين. وفي ذلك الوقت بدأ حسَّانٌ بِتنفيذ الشطر الثاني من خطته، أي القضاء على قبائل البربر العاصية، بعد أن شُفي رجاله مما أصابهم من الجراح، وبعد أن أصلحوا من أحوالهم، فسار نحو جبال الأوراس، ولمَّا عرفت الكاهنة بِمسير المُسلمين إليها، بدأت في تطبيق سياستها التي ستُمارسُها لاحقًا على نطاقٍ واسعٍ، وهي سياسة الأرض المحروقة التي تهدف إلى ترك الأرض خرابًا أمام الخصم كي لا ينتفع بِخيراتها ويزهد في الإقامة بها، فقامت بالخُروج مع رجالها من حصن باغاية ودمَّرته وأحرقته. وانسحبت القائدة البربريَّة إلى مجرى ماء يُحتمل أن يكون أحد روافد نهر مسكيانة، أو وادي مليانة ورُغم ما تقوله النُصوص من أنَّ الجيش الإسلامي كان في مركزٍ استراتيجيٍّ جيِّد في أعلى الوادي وأنَّ جُموع البربر كانت في أسفله، فإنَّ المعركة العظيمة بين الطرفين انتهت بهزيمة المُسلمين، وأسر 80 رجلاً من أشرافهم أشهرهم خالد بن يزيد العبسي الذي تبنَّتهُ الكاهنة واتخذتهُ مُستشارًا لها. وطاردت الكاهنة المُسلمين حتى خرجوا إلى برقة واضطرّوا إلى التخلَّي عن فُتوحاتهم في إفريقية والمغرب للمرَّة الثالثة خِلال عشر سنوات، ودان المغرب لها 5 سنوات. وقد أحسنت الكاهنة مُعاملة الأسرى المُسلمين ثُمَّ أطلقتهم إلَّا خالد بن يزيد بِطبيعة الحال.
نفَّذت الكاهنة خِلال غيبة المُسلمين استراتيجيَّّتها العسكريَّة سالِفة الذِكر، ويُقال أنَّها قالت للبربر: . وهكذا نزل أتباعُها يقطعون الشجر ويهدمون الحُصون ويخربون القُرى ويحرقون الزرع والضرع، فخرُبت إفريقية كُلها، وانتابت البلاد موجةٌ من الذُعر والخوف بين الأهالي من الأفارقة والبربر المدنيين والروم المُقيمين في إفريقية، فترك كثيرٌ منهم البلاد فرارًا من الكاهنة، ورحلوا في المراكب إلى جزائر البحر وكذلك إلى أيبيريا. 
لبث حسَّان في تلك الفترة ببرقة حتى جاءه المدد من عبد الملك بن مروان سنة 78هـ، فراسل حسَّانٌ خالد بن يزيد أولًا يسأله عن خبر الكاهنة، حتى أدرك أوضاعهم، ثم زحف حسَّان مُجددًا لِقتال الكاهنة والثأر لِهزيمته الأولى. وقد اقترنت عودة المُسلمين هذه المرَّة بِتغييرٍ في موازين القوى والتحالُفات السياسيَّة، إذ استقبل السُكَّان البيزنطيّون والأفارقة والبربر حسَّانًا مُستغيثين به من الكاهنة، وقدَّموا لهُ الأموال والطَّاعة. واستردَّ المُسلمون بعض القلاع مثل قابس وقفصة وقسطيلية، ودخلوا المغرب الأوسط. وعندما اقترب حسَّان من الكاهنة أدركت المرأة الغريبة بِفراستها أنَّها عاجزة عن مُواجهة المُسلمين، بعد وُصول الإمدادات إليهم وانضمام البيزنطيين والبربر إلى صُفوفهم، وعرفت أنَّ نهايتها أصبحت قريبة، لكنَّها لم تستسلم مُعتبرةً ذلك من العار، فأوغلت في جبال الأوراس لِتسحب المُسلمين خلفها، فطاردها حسَّان مُدَّة سنتين إلى أن حصل اللقاء الحاسم معها، وفي ذلك الوقت كان جيش المُسلمين قد تضخَّم كثيرًا بعد أن انضمَّ إليه المزيد والمزيد من البربر الذين اعتنقوا الإسلام، بما فيهم بعض أتباع الكاهنة الذين انتفضوا عنها شيءًا فشيئًا، ودارت بين الطرفين معركةٌ ضارية في منطقة طبرقة كثُر فيها القتل، إلَّا أنَّ النصر كان حليفُ المُسلمين، وسقطت الكاهنة قتيلةً في المعركة. بعد مقتل الكاهنة، خضع بربر تلك المناطق للمُسلمين، وانضم منهم 12 ألف إلى المُسلمين بعد أن أعلنوا إسلامهم. استعاد حسَّان بذلك القيروان، فدخلها وعمّرها مُجددًا، والتفت إلى تنظيم ولايته إداريًّا، فدوَّن الدواوين وأقام الخراج على من بقي من الروم والبربر في إفريقية على المسيحيَّة، كما ابتنى دار للصناعة بأمرٍ من عبد الملك بن مروان، ثُمَّ سار سنة 79هـ إلى دمشق بالغنائم.