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

وأعاد الحجاج بنيان الكعبة، وجعل لها بابا واحدا على ما كانت عليه قبل أن يبنيها ابن الزبير، ونقص منها ما كان ابن الزبير زاده مما يلي الحجر، وهو ستة أذرع، وكبسها بالردم الذي خرج منها، ورفع بابها على ما كان عليه، ونقص من طوله حتى صيره على ما هو عليه اليوم وفرغ من بنائها في سنة أربع وسبعون، وختم أعناق قوم من أصحاب رسول الله صلى الله عليه وسلم ليذلهم بذلك، منهم: جابر بن عبد الله، وأنس بن مالك، وسهل بن سعد الساعدي، وجماعة معهم، وكانت الخواتيم رصاصًا.

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

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

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

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

أنا ابن جلا وطلاع الثنايا ... متى أضع العمامة تعرفوني

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