Rüstəm Paşa təqribən 1500-cü ildə xorvat əsilli xristian bir ailədə Sarayevo yaxınlığındakı Butomir kəndində dünyaya gəlmişdir. Atasının Mustafa bəy olduğu, Sənan adlı qardaşı və Nəfisə adlı bir bacısı olduğu bilinməkdədir.

Gənc yaşda İstanbula gətirilərək dəvşirilən Rüstəm Paşa Əndərunda təhsil aldı. Riqab ağalığı ilə saraydan ayrıldı. 1526 tarixli Moxac Müharibəsinə silahdar olaraq qatıldı. Səfərdən döndükdən sonra birinci miraxur olaraq vəzifələndirildi. Əvvəlcə 1533-cü ildə Təkə sancaqbəyi, ardından Diyarbəkir bəylərbəyi, daha sonra isə Anadolu Bəylərbəyi təyin olundu. 1539-cu ildə vəzir-i salis (üçüncü vəzir) olaraq divana daxil oldu. Bu vəzifədə ikən 4 dekabr 1539 tarixində Şahzadə Cahangir və Şahzadə Bəyazidin sünnət mərasimində Qanuni Sultan Süleymanın qızı Mihrimah Sultanla evləndi. Bu səbəblə tarixi qeydlərdə Kürəkən Rüstəm Paşa olaraq qeyd olunur.

2 dekabr 1544 Sədrəzəm Xədim Süleyman Paşa və vəzir-i sani (ikinci vəzir) Dəli Hüsrəv Paşa arasında divan məclisi əsnasında dava çıxmış, Sultanın önündə bir-birlərinə bıçaq çıxardan paşaların hər ikisi vəzifələrindən azad edildi. Beləliklə, vəzir-i salis (üçüncü vəzir) Rüstəm Paşa sədarətə gətirildi. Bəzi tarixi mənbələrə görə, I Süleymanın nikahlı qadını olan Xürrəm Sultan kürəkəni Rüstəm Paşa vasitəsilə dövlət işlərinə müdaxilələr etmiş, öz övladlarına rəqib gördüyü Şahzadə Mustafanın edama gedən yolunu hazırlamışdır. 1553 tarixli Naxçıvan səfəri əsnasında Şahzadə Mustafa edam edilmiş, edama qarşı çıxan yeniçərilərin üsyan başlatmamaları üçün günahkar görülən Sədrəzəm Rüstəm Paşa vəzifəsindən azad edilmişdir. Yerinə Fatma Sultanın əri olan Kürəkən Qara Əhməd Paşa sədarətə gətirildi. Bu müddət ərzində iki il boyunca Üsküdardakı köşkündə yaşayan Rüstəm Paşa Xürrəm Sultan və qızı Mihrimah Sultanın yeritdikləri gizli siyasətlə Qara Əhməd Paşanın 29 sentyabr 1555 tarixində bilinməyən bir səbəblə divan məclisinin ortasında edam edilməsinin ardından yenidən sədrəzəm təyin edildi. 10 iyul 1561 tarixindəki vəfatına qədər bu vəzifədə qaldı. Cənazəsi Şahzadə külliyəsindəki türbəsində dəfn olunmuşdur.

Vəfatının ardından 12 milyon qızıl sikkədən ibarət böyük bir qaldı. Bundan başqa 1700 kölə, 2900 döyüş atı, 780.000 hasene qızıl, nağd olaraq 1000 yük qızıl pul, Anadolu və Rumelidə 815 daşınmaz əmlak,76 su dəyirmanı və 5000 cild kitabdan ibarət böyük bir kitabxanası olduğu məlum oldu. Eyni zamanda gördüyü xeyriyyə işləri ilə də adını ölümsüzləşdirən Rüstəm Paşa Xorvatiya, Macarıstan, Rumeli, İstanbul, Anadolu, Misir, Mədinə və Qüdsdə bir çox əsərlər inşa etdirmişdir. İstanbulda bir məscid, bir mədrəsə və kitabxana, 5 karvansara, 2 karvansara məscidi, 2 məktəb, Ankarada bir hamam və bir karvansara, Kastamonuda 2 məscid, Ərzincanda və Ərzurumda karvansara və hamamlar, Ədirnədə karvansara, Təkirdağda bir məscid, bir mədrəsə və kitabxana, bir məktəb, bir karvansara və bu kimi digər xeyriyyə işləri çoxdur. Ümumilikdə, 12 məscid və mədrəsə, 7 məktəb, 32 hamam, 22 çeşmə, 273 ev, 54 anbar, 563 dükan, 28 karvansara inşa etdirən Rüstəm Paşanın İstanbuldakı məscidi çiniləri ilə məşhurdur.

Rüstəm Paşa gördüyü maliyyə tədbirləri ilə xəzinəni doldurmuş, səyyahların dediyinə görə, hətta sarayın bağçasındakı gülləri belə sataraq xəzinəyə gəlir gətirmişdir. XVII əsrin mənbələrində göstərilir ki, saraydakı xəzinələr dolduğundan, dövlət xəzinəsinin bir qismi Yeddiqüllə zindanlarında saxlanmışdır.

Rüstəm Paşanın Mihrimah Sultanla olan evliliyindən Ayşə Hümaşah Sultan adlı bir qızı və Sultanzadə Osman Əfəndi adlı bir oğlu olduğu bilinir. Qızı Ayşə Sultanın nəvələrindən olan Mehmed Paşa Sultan İbrahim dönəmində sədrəzəmliyə yüksəlmişdir. Oğlu Osman bəyin və qızının 2 nəvəsinin məzarı Üsküdardakı Mihrimah Sultan məscidinin yaxınlığındadır.

• Rüstəm Paşa külliyəsi (İstanbul)
• Rüstəm Paşa külliyəsi (Təkirdağ)
• Rüstəm Paşa karvansarayı
• Rüstəm Paşa kitabxanası