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