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

فتوجه عبد الله بن ياسين مع جوهر حتى أتيا قبيلة لمتونة، وهي القبيلة التي منها يوسف بن تاشفين أمير المسلمين، ودعياها إلى العمل بشرائع الإسلام، فقالت لمتونة: أما الصلاة والصوم والزكاة فقريب، وأما قولكما من قتل يقتل، ومن سرق يقطع، ومن زنا يرجم، فهذا أمر لا نلتزمه، اذهبا عنا.

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

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

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

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