Sultan Sulejman je Rustem pašu držao “razboritim, punim vrlina i veselog duha.” Nakon službe na dvoru, postaje beglerbeg u Anadoliji i Dijarbekiru, a u Istanbul se vraća kao četvrti vezir Porte. Ženi se sa Sultanovom kćerkom, bogatom i prelijepom Mihrimah (Sunčani mjesec).Već u proljece 1541, ovaj Bošnjak biva postavljen na mjesto  drugog vezira u Carskom divanu i u tom svojstvu učestvuje u devetom velikom Sulejmanovom osvajačkom pohodu, čiji je cilj bio zauzimanje Budima. Glavna “bitka za Budim vodi se 21.VIII.1541. godine u kojoj su Bošnjaci, predvođeni tadašnjim bosanskim sandžačkim Ulama-begom, porazili i rastjerali čete Ferdinanda Habsburškog.

Nakon sto su Bošnjaci razbili opsadu Budima, janjičari su se u grad miroljubivo ušuljali i odmah putem telala objavili stanovnicima garanciju sigurnosti života i imovine, pod uvjetom da dobrovoljno predaju oružje i mirno prime janjičare. O događajima oko Budima, Rustem-paša je igrao značajnu ulogu kao diplomata i pregovarač oko mirne predaje grada Na položaj velikog vezira dolazi 1544, ali ubrzo biva okrivljen za smrt sultan-zade (princa) Mustafe, te pada u Sultanovu nemilost, pa mu je oduzet državni pečat. Međutim, vješta i moćna Roksalena,  uspjela je 1555 vratiti svog zeta na položaj velikog vezira koji je držao sve do smrti 1561.

Za vrijeme svog života, Rustem-paša je stekao ogroman imetak koji je kao vakif trošio za podizanje brojnih zadužbina. Samo u Istanbulu je sagradio džamiju, medresu, karavan-saraj, hamam, i kutubhanu (biblioteku). U Sarajevu je podigao čuveni Brusa-bezistan, han i most preko željeznice na Ilidži i druge objekte.