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