Hindistan'dan başarısız dönüş Hadim Süleyman Paşa'nın ''saldırgan'' yönetim tarzını daha da sertleştirdiği kabul edilbiliredilebilir. Önce Zebid kalesine hücum etmiştir. ''Yenilgiyi'' kabul ederek boynunda urgan ile teslim olan Zebid Beyi Nâhüda Ahmed'i idam ettirmiştir. Zebid'den geri dönüş yolunda 140 Portekizli esirin idam edilmesi sertliğinin bir başka göstergesidir.
Zebid kalesini eline gcirdiktengeçirdikten sonra bir idari reform yaparak 1539'da Yemen, Aden ve [[Zebid]]'i de içine alan Yemen Eyaleti oluşturdu. Bu eyalet valiliğine Bıyıklı Mehmet Paşa'nın oğlu Mustafa Paşa'yı vali tayin etti. Cidde'ye 31 Mart 1539'da geldi. Donanmayı Süveyş'e geri gönderip kendisi Cidde'den kara yolu ile Mekke ve Medine'ye hacca gitti. Sonra Mayısta Mısır'a geri döndü. İstanbul'dan gelen emirle Divan-ı Humayun'a rapor vermek üzere Kasım ayında İstanbul'a döndü.
