قام مقامه أبو بكر بن عمر الذي عين ابن عمه يوسف بن تاشفين أميرًا على الملثمين، لانشغاله بقتال عبدة الأصنام في جنوب المغرب، والقضاء على فتنتهم.
وكان يوسف بن تاشفين يتمتع بصفات جعلته محبوبًا؛ فهو شهم، حازم، شجاع علاوة على قدرته على القيادة والزعامة، ومهابة الناس له، مما جعل الناس تلتف حوله، وتساعده في العمليات العسكرية، ونشر تعاليم الإسلام في المغرب الأقصى، وبناء دولة المرابطين، ولما عاد أبو بكر بن عمر بعد قضائه على الفتنة وجد يوسف بن تاشفين يتمتع بمكانة عالية بين جنده ورعيته، فتنازل له رسميًّا عن السلطة وخلع نفسه وأقام مكانه ابن عمه يوسف.
اتخذ ابن تاشفين مدينة (مراكش) التي أنشأها عاصمة لملكه سنة 465هـ لتكون نقطة الانطلاق لتوحيد وتجميع قبائل المغرب الأقصى تحت سيطرته، وبناء دولة قوية، كما أنشأ أسطولاً بحريًّا، ساعده على ضم المناطق المطلة على مضيق جبل طارق مما سهل ضم المغرب الأوسط، وأقام ابن تاشفين علاقات سياسية مع جيرانه من أمراء المغرب والمشرق، كما أحاط نفسه بمجموعة من الأتباع ينظمون أمور الدولة، فأعطى دولته طابع الملك.
وفي ذلك الوقت كانت الأندلس تعاني من التفكك تحت حكم ملوك الطوائف الذين كانوا يواجهون خطر غزوات المسيحيين، وسيطرة ملوكهم وتعسفهم في مطالبة الولاة المسلمين بما لا طاقة لهم به، وكان يوسف يفكر في حال المسلمين في بلاد الأندلس وما يفعله النصارى بهم ويتجه إلى الله تعالى مستخيرًا إياه يتلمس منه النصر، وكان إذا أجبر على الكلام قال: أنا أول منتدب لنصرة هذا الدين، ولا يتولى هذا الأمر إلا أنا.
واستنجد أمراء الأندلس بابن تاشفين لينقذهم من النصارى وكان على رأس من استنجد به (المعتمد بن عباد) أمير إشبيلية، فأعد ابن تاشفين جيشه وقبل أن يعبر البحر نحو الأندلس بسط يديه بالدعاء نحو السماء قائلاً: اللهم إن كنت تعلم أن في جوازنا أي (اجتياز البحر) هذا خيرًا للمسلمين، فسهل علينا جواز هذا البحر، وإن كان غير ذلك فصعبه حتى لا أجوزه.
والتقي بجيش النصارى بقيادة ألفونسو السادس في موقعة (الزلاقة) سنة 480هـ/1087م وانتصر جيش ابن تاشفين انتصارًا هائلاً، وبعدها وحَّد المغرب والأندلس تحت قيادته الخاصة، ورأى شيوخ المرابطين ما يقوم به يوسف من أعمال عظيمة فاجتمعوا عليه وقالوا له: أنت خليفة الله في المغرب وحقك أكبر من أن تدعى بالأمير، بل ندعوك بأمير المؤمنين، فقال لهم: حاشا لله أن أتسمى بهذا الاسم، إنما يتسمى به الخلفاء، وأنا رجل الخليفة العباسي، والقائم بدعوته في بلاد المغرب، فقالوا له: لابد من اسم تمتاز به، فقال لهم: يكون (أمير المسلمين).
وبعد انتهاء موقعة الزلاقة بايعه من شهدها معه من ملوك الأندلس وأمرائها أميرًا على المسلمين، وكانوا ثلاثة عشر ملكًا، واستطاع يوسف بن تاشفين أن يوقف زحف جيوش النصارى، وأن يعيد ما استولوا عليه من الأندلس، وقد امتدت دولته فشملت الأندلس والمغرب الأقصى، وازدهرت البلاد في عصره، وضرب السكة (أي العملة) ونقش ديناره: لا إله إلا الله محمد رسول الله، وتحت ذلك: أمير المسلمين