Halk arasında “gazi” ve bilhassa gözünü budaktan sakınmaz tavrı ve hareketleri neticesinde “deli” lakabı ile tanınmış olan Hüseyin Paşa, kuvvetli bir vücut yapısına sahip, cesur bir vezirdi. Özellikle Revan ve Bağdat seferleri ile Girit’in fethinde gösterdiği kahramanlıklar, kendisine büyük bir şöhret kazandırdı. Girit’te 12 yıl geceli gündüzlü cephede kalmış ve bütün parasını adanın imarına harcamıştı. Bu sebeple halk arasında ziyadesiyle sayılıp seviliyordu. Bilhassa Girit Rumları arasında İslamiyetin yayılmasına gayret etmiş ve onun gösterdiği adalete hayran kalan Hıristiyanlar, kitleler halinde İslam'a girmişlerdir. Bu, Arnavutluk ve Bosna-Hersek’tekinden sonra Balkan kavimleri arasında üçüncü toplu İslamlaşma hareketidir. Bazı kiliseleri camiye çevirtip, Hanya ve Kandiye başta olmak üzere pek çok yerde cami yaptırdı.
Hüseyin Paşa, son derece kuvvetliydi. Rivayete göre İstanbul’a gelen İran elçisi memleketinden getirdiği bir yayı Sultan Dördüncü Murad’a takdim etmişti. Kurulu bir vaziyette bulunan yayın özelliği, boşaltıp yeniden kurmanın son derece zor olmasıydı. Nitekim sarayda tertip olunan bir müsabakada hiçbir şahıs bu yayı boşaltamamış ve padişah yayın Ağa Kapısına asılmasını ve bu işi yapacak olan şahsın kendisine bildirilmesini istemişti. Bu arada Ağa dairesinde hizmet etmekte olan Hüseyin Paşa, yayı kurup boşaltmış ve durum Sultan Murad’a bildirilmişti. Hüseyin Paşa, daha sonra aynı hareketi Sultan’ın ve İran elçisinin huzurunda birkaç defa tekrarlayınca, Sultan, pek beğendiği bu genci bir daha yanından ayırmamıştı.