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