Rüstem Paşa, yaklaşık olarak 1500 yılında Hırvat asıllı Hristiyan bir ailenin çocuğu olarak Saraybosna yakınlarındaki Butmir veya Sarajevsko Polje adlı bir köyde doğduğu varsayılmaktadır. Babası Mustafa Bey (Paşa) olup, Sinan (Kaptan-ı Derya Sinan Paşa) ve Nefise adında iki kardeşi bulunmaktadır. Küçük yaşlarda İstanbul'a getirilen Rüstem Paşa, Enderun'da eğitim görmüştür. Osmanlı topraklarına getirildikten sonra devşirilmiş ve Osmanlı İmparatorluğu'nun hizmetine girmiştir.

Rüstem Paşa, 1526 yılında Mohaç Meydan Muharebesi'ne silahtar rütbesi ile katılmıştır. Bu seferin sonunda birinci imrahor görevine atanmıştır. Üstün yeteneği ve kıvrak zekâsı ile Sultan Süleyman'ın dikkatini çekmeyi başarmıştır. Sultan Süleyman’ın emriyle Diyarbakır'da beylerbeyi olarak atanmış ve hizmetine burada devam etmiştir. Bu görevindeki başarısından dolayı daha sonra Anadolu Beylerbeyliği'ne atanmış ve burada görevine devam etmiştir. 1539 yılında Sultan Süleyman’ın Rüstem Paşa’yı yanında istemesi ile üçüncü vezirlik görevine tayin edilmiştir.

Üçüncü vezir görevini devam ettirirken, 26 Kasım 1539 tarihinde Şehzade Cihangir ve Şehzade Bayezid'in sünnet töreninde Sultan Süleyman'ın kızı Mihrimah Sultan ile evlenmiştir. Bu evlilikle birlikte "damat" sıfatını almıştır. Ancak, Rüstem Paşa’nın bu evliliği bazı rakiplerinin onu çekememesine neden olmuş ve onun cüzzam hastası olduğu dedikodusunu yaymışlardır. Bu dedikodular üzerine hassa hekimlerinden Mehmet Halife, Rüstem Paşa'yı detaylı bir şekilde muayene etmiş ve cüzzam hastası olmadığını belirlemiştir. Bu olaydan sonra Rüstem Paşa, "Kehle-i İkbal" (İkbal Biti) olarak anılmıştır.

1544 yılında Kanuni Sultan Süleyman, Hadım Süleyman Paşa'yı görevden azledince, yerine geçmesi beklenen ikinci Vezir Deli Hüsrev Paşa ile arasında husumet çıkararak Rüstem Paşa’nın sadrazamlık görevine getirilmesini sağlamıştır. Bu süreçte Hürrem Sultan’ın desteği büyük rol oynamıştır. Rüstem Paşa, sadrazamlık görevini 1553 yılına kadar sürdürmüştür. Bu dönemde, Hürrem Sultan ile birlikte Şehzade Mustafa’ya karşı entrikalar düzenleyerek, onun Kanuni Sultan Süleyman’a karşı tahtta gözü olduğu iftirasını ortaya atmışlardır. Bu iftira sonucunda Şehzade Mustafa katledilmiştir. Yeniçerilerin ayaklanma endişesi nedeniyle 1553 yılında Rüstem Paşa görevden azledilmiş ve yerine Kara Ahmet Paşa getirilmiştir.

Hürrem Sultan ve Mihrimah Sultan’ın çabalarıyla, Rüstem Paşa 29 Eylül 1555 tarihinde tekrar sadrazamlık görevine getirilmiştir. Kara Ahmet Paşa, Divan-ı Humayun’un ortasında idam edilmiştir.

Rüstem Paşa, Mihrimah Sultan ile evliliğinden olan kızı Ayşe Sultan’ın vebaya yakalandığını öğrendikten sonra kahrolmuş ve kızının iyileşmesi için elinden gelen her şeyi yapmıştır. Ancak, bu süreçte kendisi de hastalığa yakalanmış ve 10 Temmuz 1562'de hayatını kaybetmiştir. Rüstem Paşa’nın cenazesi Şehzade Camii bahçesindeki türbede gömülüdür.

Rüstem Paşa, Osmanlı Devleti’ne rüşveti getiren kişi olarak anılmaktadır. Rüşvet alma işini aleni bir şekilde yapmaktan çekinmemiş ve belli bir tarifeye bağlamıştır. Bu nedenle Osmanlı kaynaklarında "Ebvab-ı Rüşvet Fatihi" (Rüşvet Kapısını Fetheden Kişi) olarak anılmıştır. Rüstem Paşa’nın mal varlığı dillere destandır ve padişahtan sonraki en zengin kişi olduğu söylenmektedir.

Rüstem Paşa’nın birçok mimari eseri bulunmaktadır:

Bu eserlerden Kütahya'daki hamam günümüze kadar ulaşmıştır. Medrese ise daha sonra orijinaline uygun olarak yeniden restore edilmiştir.