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