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