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