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