على بن يوسف ، مالك بن وهيب ، چون از قضيه آگاه شد امير را به دفع او ترغيب كرد . اين مرد با نگريستن در احوال كواكب از حوادث آينده خبر مىداد . كاهنان گفته بودند كه در مغرب در ميان امتى از بربر پادشاهى پديد خواهد آمد كه شكل سكه را تغيير مىدهد و اين به هنگامى است كه ميان دو كوكب از كواكب علوى سياره قران حاصل شود . امير همواره منتظر ظهور اين قرآن بود از اين رو ابن وهيب او را گفت كه دولت خود نگه دار كه اين مرد صاحب همان قران است . و راجع به آن درهم مربع شكل ، مردم كوچه بازار سجعى سخيف ساخته بودند و مىخواندند :
اجعل على رجله كبلا * لئلا يسمعك طبلا
و مىپنداشتند كسى كه آن درهم مربع را رواج خواهد داد اوست . على بن يوسف بن تاشفين او را طلب داشت ولى مهدى ناپديد شده بود . سوارانى به جستجويش فرستاد ، نيافتندش .
با عامل سوس ابو بكر بن محمد لمتونى يكى از قبيلهء هرغه را به كشتن او بر گمارد . ياران او را هشدار دادند و ايشان امام را به درون پناهگاهى منيع بردند و كسانى را كه متهم به اين توطئه بودند به قتل آوردند . محمد بن تومرت مصامده را به بيعت خود دعوت كرد ، به دو شرط يكى ايمان به توحيد و يكى قتال با مجسمه در ركاب او . اين دعوت در سال 515 علنى گرديد . آنگاه چند تن از رجال خود را كه برخى از ده نفر نخستين ( اهل عشره ) بودند به نزد قبايل فرستادند و در زمرهء آنان بودند از هنتاته ابو حفص عمر بن يحيى و ابو يحيى بن يكيت و يوسف بن وانودين و ابن يغمور و از تينملل ، ابو حفص عمر بن على اصناك و محمد بن سليمان و عمر بن تافراكين و عبد اللّه بن ملويات . در قبيلهء هرغه جوش و خروشى پديد آمد و همه در بيعت او در آمدند . سپس قبايل كدميوه و كنفيسه هم با آنان همرأى شدند . چون كار بيعت كامل شد او را المهدى لقب دادند و حال آنكه پيش از آن او را امام لقب داده بودند .
اصحابش را « طلبه » مىگفتند و پيروانش را « موحدين » چون شمار يارانش به پنجاه تن رسيد آنان را اهل خمسين خواند . عامل سوس ابو بكر بن محمد لمتونى به سركوبى ايشان در حركت آمد و رهسپار قبيلهء هرغه شد . آنان نيز برادران خود را از هنتاته و تينملل گرد آوردند و بر آنان تاختند و سپاه لمتونه را فرو كوفتند و اين سرآغاز پيروزى بود و امام آنان را به اين پيروزى وعده داده بود . چون پيروزى حاصل شد به ديدهء ديگر در او نگريستند و در قبول دعوت و بيعت با او بر يك ديگر پيشى گرفتند . سپاهيان لمتونه پى در پى بر سر ايشان مىتاختند و هر بار شكست مىخوردند . پس از سه سال كه از بيعتش گذشته بود به كوه قبايل تينملل نقل مكان كرد و آنجا را وطنگاه خويش ساخت و براى خود خانهاى و مسجدى در حوالى سرچشمهء رود نفيس در ميان آنان بنا نمود .
سپس به جنگ آن گروه از مصامده كه از بيعتش سر برتافته بود ، لشكر كشيد و جنگيد تا به راهشان آورد . نخست با قبيلهء هرزجه جنگيد و بارها سركوبشان نمود تا به اطاعت