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