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

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

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