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