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

مضى تميم بن المعز بن باديس لدعم بنيان دولته. فقاد في السنة التالية (458 ه = 1045 م) جبشأ كثيفا، وسار به إلى تونس التي كانت قد خرجت عن الطاعة منذ أيام أبيه. ومر بطريقه على القيروان، فعرف حاكمها - قائد بن ميمون - أنه لا طاقة له بتميم وجيشه، فترك القيروان التي دخلها تميم، ثم سار منها إلى - قابس - فامتنع حاكمها - ابن خراسان - فحاصره تميم لمدة سنة وشهرين حتى أخضعه و جابه تميم موقفة صعبة سنة 476 ه = 1083 م، إذ عمل مالك بن علوي الصخري على جمع العرب، فأكثر، وسار بهم إلى المهدية. وحاصرها. فنهض له تميم بن المعز وطرده، فسار مالك منها إلى القيروان فحاصرها واستولى عليها، فوجه إليه تميم جيشا كبيرة، مما أرغم