Kardeşi Velid'in vefatı gününde, yani hicri doksanaltmcı senenin cemaziyelahir ayının ortalarında cumartesi günü Remle'de kendisinin halifeliğine bey'at edildi. Süleyman, babaları Abdülmelik'in vasiyeti üzerine kardeşi Velid'den sonrası için veliahd tayin edilmişti. Velid, ölmeden önce kardeşi Süleyman'ı veliahtlıktan hal etmek ve yerine kendi oğlu Abdülaziz'i veliaht tayin etmek istemişti. Haccac'da bu hususta ona uymuş ve tavsiyede bulunmuştu. Kuteybe b. Müslim ile bir cemaatta bu hususta ona muvafakatlarım bildirmişlerdi. Cerir ve diğer şairler, bu hususta şiirler ve kasideler söylemişlerdi. Ancak Ve-Hd'in vefatına kadar bu iş gerçekleştirilemedi. Vefat edince de direkt olarak Süleyman'ın halifeliğine bey'at edildi. Kuteybe b. Müslim, ona tehdit savurdu ve bey'at etmemeye azmetti. Ancak Süleyman, onu azletti. Yerine Irak ve sonra da Horasan valiliğine Yezid b. Mühelleb'i tayin etti. Fakat aradan on sene geçtikten sonra onu tekrar valiliğe iade etti ve Haccac b. Yusuf ailesini cezalandırmasını ona emretti. Çünkü daha önceleri Haccac, Yezid'i Horasan'dan azletmişti. Bu senenin ramazan ayının bitimine yedi gün kala Süleyman, Osman b. Hayyan'ı Medine valiliğinden azletti. Yerine Ebu Bekir b. Muhammed b. Anır b. Hazm'ı tayin etti. Bu zat, âlimlerden biri idi.
Kuteybe b. Müslim, Süleyman'ın halifeliğe geçtiğini duyunca ona bir mektup yazarak kardeşi Velid'in ölümü nedeniyle taziyetlerini sundu, başsağlığı diledi. Halifeliğini tebrik etti. Çektiği mihnetleri, sıkıntıları, düşmana karşı heybet ve savaşlarını, Allah'ın kendisine nasib ettiği fütuhatı, büyük beldelerle şehirleri ve iklimleri eliyle fet-hedişini dile getirdi. Ayrıca daha önce Velid'e gösterdiği itaatkarlığı kendisine de göstereceğini, ona gösterdiği samimiyyeti kendisine de sergileyeceğini ve nasihat vereceğini ifade etti. Tabii bütün bunları, kendisini Horasan valiliğinden azletmemesi şartına da bağladı. Bu mektubunda Yezid b. Mühelleb'in aleyhinde ifadeler kullandı.
Sonra ikinci bir mektup yazdı. Yine bu mektubunda gerçekleştirdiği fetihleri, yaptığı savaşları, hükümdarlar ve Acemler karşısındaki heybetini anlattı. Yezid b. Mühelleb'i yine yerdi. Mektubunda eğer kendisini Horasan valiliğinden alıp yerine Yezid'i tayin edecek olursa, Süleyman'ı halifelikten hal' edeceğine yemin etti.
Üçüncü bir mektup yazarak bu mektubunda Süleyman'ı tümden halifelikten hal' ettiğini ifade etti ve bunu bir ulakla halife Süleyman'a gönderdi. Gönderirken de ulağa şu tenbihatı yaptı:
"Süleyman'a birinci mektubu ver. Eğer mektubu okuyup Yezid b. Mühelleb'e verirse, ona ikinci mektubu da ver. Eğer o mektubu da okuyup Yezd b. Mühelleb'e verecek olursa, ona üçüncü mektubu ver."
Ulak gitti. Süleyman, birinci mektubu okurken tesadüfen Yezid b. Mühelleb de yanına geldi. Okuduktan sonra mektubu Yezid'e verdi. Yezid de okudu. Bu defa ulak, ikinci mektubu Süleyman'a verdi. Süleyman, mektubu okuduktan sonra Yezid'e verdi. Sonunda ulak, üçüncü mektubu da verdi. Süleyman, mektubu okuyunca mektupta Kuteybe'nin kendisini halifelikten hal' ettiğini açıkça söylediğini gör-, büzünün rengi değişti, sonra mektubu kapatıp elinde tuttu. Ye-zıd'e vermedi, ulağın misafirhaneye götürülmesini emretti. Geceleyin haber göndererek ulağı yanma çağırttı. Ulağa altınlar verdi, bir de mektup verdi ki, mektupta Kuteybe'yi Horasan'a vali tayin ettiğini ifade ediyordu. Bu ulakla beraber kendi tarafından başka bir ulakta gönderdi ki, kendisini Horasan valiliğinde bıraktığım ona bizzat ifade etsin. Ulakların ikisi de Horasan'a ulaştıklarında Kuteybe'nin, halife Süleyman'ı hilafetten hal' ettiğini duydular. Süleyman'ın ulağı, yanındaki mektubu Kuteybe'nin ulağına verdi. Sonra ikisi de, -Süleyman'ın ulağı geri dönmeden önce- Kuteybe'nin öldürülmüş olduğunu duydular.