Rüstem Paşa, yaklaşık 1500 yılında Hırvat asıllı hristiyan bir ailenin çocuğu olarak Saraybosna yakınlarında olan ya Butomır ya da Sarajovska Polje adlı bir köyde doğmuştur.[1] Ailesinin adının Öpüçoviç veya Cığaliç olduğu bildirilmektedir. Babası Mustafa Bey (Paşa) olup Sinan (Kaptan-ı derya Sinan Paşa o. 1554) ve Nefise adlı iki kardeşi olduğu belirtilmektedir.

Genç yaşta İstanbul'a getirilip devşirilen Rüstem Paşa Enderun'da eğitim gördü. Enderundan rikâb ağalığı ile çıktı. 1526 Mohaç Muharebesi'ne silahdar olarak katıldı. Bu seferden döndükten sonra birinci imrahor görevine tayin edildi. Üstün yetenekleri dolayısıyla Sultan Süleyman'ın gözüne girdi. Önce Diyarbakır beylerbeyi oldu. Sonra Anadolu beylerbeyliğine nakledildi. 1539'da ....