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