Rustem Pascià era anche conosciuto come Damat (genero in turco) perché sposò la figlia del sultano Solimano. La sua data esatta di nascita nel XVI secolo e la posizione è sconosciuta. Le fonti forniscono date e luoghi diversi per Rüstem Pascià; si crede che sia nato in un villaggio della Bosnia, molto probabilmente a Butmir o Skradin.
Da bambino fu portato a Istanbul, allora capitale dell'Impero Ottomano, e studiò per essere un futuro servitore dello stato ottomano. Divenne governatore (Beylerbeyi) di Diyarbakir nel 1539. Promosse rapidamente sposando Mihrimah Sultan, figlia del sultano Solimano il Magnifico, e divenne prima visir e poi gran visir del sultano nel 1544. Servì per 15 anni al palazzo, fino alla sua morte il 10 luglio 1561 e fu sepolto nel suo mausoleo nel cortile della moschea Sehzade a Istanbul.
Rüstem Pascià era intelligente e aveva una mente orientata al commercio. Possedette terreni e molti edifici, raccolse gli affitti da questi e divenne molto ricco. In realtà si dice che fosse la persona più ricca dopo i sultani. Fece costruire caravanserragli, hammam, madrasse e moschee per il suo nome. La moschea Rüstem Pascià ad Istanbul ha il miglior esempio di piastrelle e arte ottomana.