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