El día de la muerte de su hermano Walīd, es decir, un sábado a mediados del mes de Jumādā al-Ākhira del año noventa y seis de la Hégira, se prestó el juramento de lealtad (bayʿa) a Sulaymān como califa en Ramla. Sulaymān había sido designado heredero tras su hermano Walīd, según el testamento de su padre ʿAbd al-Malik. Antes de morir, Walīd quiso destituir a su hermano Sulaymān de la sucesión y nombrar en su lugar a su propio hijo ʿAbd al-ʿAzīz como heredero. Al-Ḥajjāj le apoyó en este asunto y le aconsejó en consecuencia. Qutayba b. Muslim y un grupo también le manifestaron su acuerdo. Jarīr y otros poetas compusieron poemas y odas sobre este tema. Sin embargo, este asunto no se concretó antes de la muerte de Walīd. Al fallecer, se prestó inmediatamente el juramento de lealtad a Sulaymān como califa. Qutayba b. Muslim lo amenazó y decidió no prestarle juramento. Sin embargo, Sulaymān lo destituyó. En su lugar, nombró a Yazīd b. al-Muhallab como gobernador de Irak y luego de Jorasán. Sin embargo, tras diez años, lo restituyó en el cargo y le ordenó castigar a la familia de al-Ḥajjāj b. Yūsuf, ya que anteriormente al-Ḥajjāj había destituido a Yazīd de Jorasán. Siete días antes del final del mes de Ramadán de ese año, Sulaymān destituyó a ʿUthmān b. Ḥayyān del gobierno de Medina y nombró en su lugar a Abū Bakr b. Muḥammad b. Amr b. Ḥazm. Este era uno de los sabios.
Cuando Qutayba b. Muslim supo que Sulaymān había accedido al califato, le escribió una carta presentándole sus condolencias por la muerte de su hermano Walīd y expresándole su pésame. Le felicitó por su acceso al califato. Relató las pruebas y dificultades que había soportado, su imponencia y combates contra el enemigo, las conquistas (futūḥāt) que Allah le había concedido, y las grandes ciudades y regiones que había conquistado por su mano. Además, manifestó que mostraría a Sulaymān la misma obediencia, sinceridad y consejo que había mostrado a Walīd, a condición de que no lo destituyera del gobierno de Jorasán. En esta carta, habló en contra de Yazīd b. al-Muhallab.
Luego escribió una segunda carta. En esta también describió sus conquistas, batallas y su imponencia ante los gobernantes y los persas. De nuevo, criticó a Yazīd b. al-Muhallab. En la carta, juró que si Sulaymān lo destituía del gobierno de Jorasán y nombraba a Yazīd en su lugar, destituiría a Sulaymān del califato.
Escribió una tercera carta, en la que expresamente declaró que había destituido a Sulaymān del califato, y la envió al califa Sulaymān con un mensajero. Al enviarla, dio al mensajero las siguientes instrucciones:
"Entrega a Sulaymān la primera carta. Si la lee y se la da a Yazīd b. al-Muhallab, entonces dale la segunda carta. Si lee esa y se la da a Yazīd b. al-Muhallab, entonces dale la tercera carta."
El mensajero partió. Mientras Sulaymān leía la primera carta, Yazīd b. al-Muhallab llegó casualmente. Tras leerla, Sulaymān se la dio a Yazīd, quien también la leyó. Entonces el mensajero entregó a Sulaymān la segunda carta. Tras leerla, Sulaymān se la dio a Yazīd. Finalmente, el mensajero le entregó la tercera carta. Cuando Sulaymān la leyó, vio que Qutayba había declarado expresamente su destitución del califato; su rostro cambió de color, luego cerró la carta y la retuvo en su mano, sin dársela a Yazīd. Ordenó que el mensajero fuera llevado a la casa de huéspedes. Por la noche, envió aviso y mandó llamar al mensajero. Le dio oro y una carta en la que expresaba que había nombrado a Qutayba gobernador de Jorasán. Junto con este mensajero, envió otro de su confianza para informar personalmente a Qutayba de que lo mantenía en el gobierno de Jorasán. Cuando ambos mensajeros llegaron a Jorasán, supieron que Qutayba había declarado depuesto al califa Sulaymān. El mensajero de Sulaymān entregó su carta al mensajero de Qutayba. Luego, antes de que el mensajero de Sulaymān pudiera regresar, ambos supieron que Qutayba había sido asesinado.