بعد فترة عهد الفتح بدأ عهد جديد يسمى: عهد الولاة، بدأ بعد رجوع موسى بن نصير وطارق بن زياد إلى دمشق، أي: من سنة (96) من الهجرة ويستمر حتى سنة (138) من الهجرة، أي: حوالي (42) سنة، وعهد الولاة هو أن يتولى حكم الأندلس في هذه الفترة وال يتبع الحاكم العام للمسلمين وهو الخليفة الأموي الموجود في بلاد الشام في دمشق، ويعتبر سليمان بن عبد الملك في أول عهد الولاة، ثم توالى من بعده الحكام من بني أمية؛ عمر بن عبد العزيز، ثم يزيد بن عبد الملك، ثم هشام بن عبد الملك وهكذا إلى آخر الدولة الأموية.
وكان أول الولاة على منطقة الأندلس هو عبد العزيز بن موسى بن نصير بأمر من سليمان بن عبد الملك رحمه الله، وهذا الرجل كان كأبيه في جهاده وتقواه وورعه كما يقول عنه أبوه موسى بن نصير: لقد عرفته صواماً قواماً، وكان مجاهداً في سبيل الله، ووطد الأركان بشدة في منطقة الأندلس، وتوالى من بعده الولاة.
تولى من الولاة على منطقة الأندلس خلال (42) سنة حوالي (22) أو (20) والياً، يعني: أن كل وال لا يحكم إلا سنتين أو ثلاثاً، فلماذا هذا التغيير المفاجئ للولاة والتغيير الكثير في الولاة؟ مما لا شك فيه أن هذا التغيير الكثير بسبب استشهاد كثير من الولاة في معاركهم في بلاد فرنسا، وأما في الفترة الثانية من عهد الولاة، فكان الولاة يغيرون بالمكائد والانقلابات والمؤامرات وما إلى ذلك، فالفترة الأولى تختلف بالكلية عن الفترة الثانية.