والأثبج وزغبة ورياح وربيعة وعدي. وكانوا يزحفون أحياناً إلى أطراف العراق والشام، ويقطعون الطرق، ويفسدون السابلة، وأحياناً كان بنو سليم يعتدون على الحاج أيام موسمهم بمكة، وأيام الزيارة بالمدينة. واستمرت البعوث والكتائب تجهز لمعاقبتهم، وحماية الحاج من شرهم، ولكن دون جدوى. ولما ظهر القرامطة بالبحرين في أوائل القرن الرابع الهجري لحق بهم بنو سليم، وبنو هلال، وكثير من بطون ربيعة بن عامر. ولما تغلب القرامطة على الشام، وأخذوا يهددون مصر، وظفر الخليفة العزيز بالله بهزيمتهم وردهم، استبقى أشياعهم من العرب من بني هلال وسليم بمصر، وأنزلهم بالصعيد وفي الصحراء الشرقية، فأقاموا هنالك، ولكنهم لم ينقطعوا عن عيثهم وفسادهم.
وهنا تأتي قصة نزوحهم إلى إفريقية. وكان المعز لدين الله الفاطمي، حينما انتقل من إفريقية إلى مصر في سنة ٣٦١ هـ، قد استخلف على إفريقية يوسف بن زيري بن مناد الصنهاجي ليحكم باسم الخلافة الفاطمية وتحت سيادتها. ثم تطورت الظروف وعمل آل زيري على تدعيم استقلالهم، حتى فسد الأمر بينهم وبين الخلافة الفاطمية، فخلعوا طاعتها الإسمية، وأعلن المعز بن باديس الصنهاجي انضواءه تحت لواء الخلافة العباسية (سنة ٤٣٧ هـ)، فعز ذلك على الخلافة الفاطمية، وغضب الخليفة المستنصر بالله، وأخذ البلاط الفاطمي يبحث عما يمكن فعله لمقابلة هذا الإجراء، الذي اعتبر خروجاً على الخلافة الفاطمية، واعتداء على حقوقها الشرعية.
وكان العرب من بني سليم وهلال الذين أنزلوا بالصعيد قد تكاثروا، وتفاقم عيثهم وشرهم، فأشار الوزير أبو محمد الحسن بن علي اليازوري، على الخليفة المستنصر باستمالة أشياخهم، وتقليدهم أعمال إفريقية وشئونها، ليكونوا هنالك أولياء للدعوة الشيعية، وليعملوا على نصرتها إزاء آل زيري المنتزين عليها، فإن نجحت الفكرة وبقى أولئك على ولائهم، كان ذلك كسباً للخلافة الفاطمية وتقوية لجانبها، هذا فضلا عن انقطاع عيثهم بنواحي مصر، وإن كان الأمر بالعكس فهم وشأنهم. فوافق المستنصر على ذلك الرأي، وبعث وزيره إلى العرب في سنة ٥٤١ هـ، فسار إلى أحيائهم، وبذل العطاء الوفير لأشياخهم، وفرق في عامتهم بعيراً وديناراً لكل منهم، وأباح لهم عبور النيل، وقال لهم قد أعطيناكم مُلك المغرب، ومُلك المعز بن باديس.