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