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