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