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