Jabarkan Khalifah dari Sulaiman bin Abdul Malik

Selama menjadi gubernur, Sulaiman berkeyakinan bahwa alih-alih menumbuhkan kesetiaan, pemerintahan Al-Hajjaj justru menyuburkan rasa benci rakyat Iraq pada Umayyah. Hal ini menjadikan Sulaiman melucuti kedudukan banyak para pejabat provinsi yang ditunjuk Khalifah Al-Walid dan Al-Hajjaj pada tahun pertamanya menjadi khalifah.

Al-Hajjaj sendiri meninggal pada masa kekuasaan Al-Walid, tetapi keluarganya disiksa dan harta mereka disita atas perintah Sulaiman. Musa bin Nushair yang dipandang berupaya mendirikan dinastinya sendiri di Afrika Utara dan Al-Andalus kemudian diberhentikan dan menghabiskan masa pensiun di Madinah. Putra Musa, 'Abdul 'Aziz bin Musa, dibunuh dan kepalanya dikirim kepada Sulaiman saat Musa bin Nushair juga ada di sana. Sebagian pendapat menyatakan bahwa Sulaiman yang memberi perintah atas hal tersebut, tetapi Ibnu Khaldun berpendapat bahwa perintah itu dari Habib bin Abu 'Ubaidah, keturunan bangsawan Arab di Kairouan. Beberapa hal yang ditengarai menjadi penyebab peristiwa tersebut adalah 'Abdul 'Aziz bin Musa dikatakan telah menjadi Kristen lantaran terpengaruh istrinya, Permaisuri Egilona, janda Raja Roderikus, meski sangat mungkin bahwa kabar tersebut disebarkan oleh lawan politiknya. Atas desakan Qutaibah, Sulaiman mempertahankan kedudukannya sebagai Gubernur Khurasan, tetapi Qutaibah sendiri kemudian dikudeta dan dibunuh pasukannya sendiri yang dipimpin Waki bin Abi Sud lantaran sang gubernur berusaha mengkhianati Sulaiman. Muhammad bin Qasim sendiri ditahan dan dihukum mati atas pengaruh Salih bin 'Abdurrahman, pejabat berpengaruh di kawasan Iraq, yang kerabatnya ditahan dan dihukum mati oleh Al-Hajjaj.

Sebagian sejarawan menyatakan bahwa masa kekuasaan Sulaiman merupakan kembalinya kekuatan politik kelompok Yamani, sebagian lain menyatakan bahwa tidak ada tanda-tanda Sulaiman mengunggulkan satu kelompok atas lainnya. Sulaiman sendiri juga menjalin hubungan dekat dengan pasukan kelompok Qays di Mesopotamia Hulu.

Setelah melucuti kekuatan lawan-lawan politiknya, Sulaiman menempatkan orang-orang kepercayaannya menggantikan mereka. Yazid bin Muhallab ditetapkan sebagai Gubernur Iraq. Waki bin Abi Sud menyatakan dirinya sebagai Gubernur Khurasan sepeninggal Qutaibah dan Sulaiman mengakui kedudukannya, meski Sulaiman membatasi kekuasaannya hanya dalam urusan militer. Sepupu Sulaiman, 'Umar bin 'Abdul 'Aziz yang dulu diberhentikan menjadi Gubernur Madinah oleh Al-Walid atas usulan Al-Hajjaj kemudian menjadi tangan kanan dan penasihat utama khalifah. Sulaiman sendiri kemudian memerintahkan pembebasan tahanan politik di kawasan Iran dan Iraq yang pada umumnya adalah pendukung ahlul bait.

Terdapat beberapa pendapat mengenai kebijakan Sulaiman ini. Sebagian menyatakan bahwa kebijakan ini merupakan awal dari menurunnya kekuasaan Umayyah lantaran tokoh-tokoh yang diberhentikan ini merupakan sosok berpengaruh yang memberi sumbangsih materi besar atas kekhalifahan. Namun dalam sudut pandang lain, berbagai keputusan ini dipandang tepat lantaran perilaku keagamaan para pejabat baru yang lebih baik dan kebijakan mereka yang lebih akomodatif dengan suara rakyat. Hal ini membalikkan persepsi rakyat di berbagai kawasan untuk lebih menerima kekuasaan Umayyah.