ولم يقتصر نصر شبيب على إصابة الحجاج بالعار والخزي بل أصابه أيضا في الخراج الذي يجبيه من هذه النواحي فقد ضاع عليه خراج مناطق واسعة ونهبت دور المال. فبعث مرة أخرى جيشا قويا من أهل الكوفة بقيادة عبد الرحمن بن مجمد بن الأشعث المشهور. وخرج عبد الرحمن بن الأشعث الكندي في الناس حتى مر بالمدائن وأتى الجزل - سلفه ومن بين قومه - فسأله عن جراحته وأوصاه الجزل بخطة في القتال وعاها عبد الرحمن وخرج بالناس نحو شبيب. فلما دنا منه ارتفع عنه شبيب إلى دقوقاء وشهرزور واستمر في طلبه حتى ترك شبيب نواحي المدائن وأذن له الحجاج بالسلوك في إثره أين سلك حتى يدركه فيقتله أو ينفيه.
فسار عبد الرحمن في إثر شبيب حتى وصل نهر حولايا على تخوم الموصل الفاصلة بين نواحي الموصل وسواد الكوفة وقد كانت خطة شبيب أن يرهق جيش عبد الرحمن بحمله على السير في إثره في طريق ملتوية في أرض جبلية وعرة ولم يجد شبيب فرصة لمفاجأته. ولكن الحجاج لم يطق صبرا على هذه الخطة المراوغة المطاولة فعزل عبد الرحمن وأمر مكانه عثمان بن قطن الحارثي (1). إذ الأول شديد الحذر والثاني مغامر. أراد عثمان أن يمسك بالثور من قرنيه فكان الاخفاق جزاءه. ففي يوم الخميس العاشر من ذي الحجة سنة 76 ه‍ (الثلاثاء العشرين من مارس سنة 696 م) نشب القتال بينه وبين شبيب كانت الدائرة على عثمان فهزم وقتل. وعاد عبد الرحمن بن الأشعث بالفلول المنهزمة إلى دير أبي مريم ومن ثم إلى الكوفة.
وقام شبيب في شتاء سنة 76 ه‍ (695 / 696 م) ببعض الغارات. ولكي يستجم هو وأصحابه أتى في مستهل سنة 77 ه‍ (إبريل سنة 696 م) إلى جبال ماء بهراذان (2) فصيف بها ثلاثة أشهر وهناك انضم إليه ناس كثيرون بعضهم ممن كان الحجاج يطلبهم بمال أو تباعات (تارات). فلما انتهى الحر خرج من ماه بهراذان وأقبل نحو المدائن وكان عليها من قبل الحجاج مطرف بن المغيرة بن شعبة ولم يكن