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