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