Мечеть, построенная в 1561 г. зодчим Мимар Синаном по приказу Рустам Паши, знаменитого оттоманского Садразама (великий визирь) хорватского происхождения, женившегося на дочери султана Сулеймана Великолепного (Кануни) Михримах Султан, очень далека от скромных произведений Мимар Синана. Элементами отдалившими мечеть от простоты стиля Мимар Синана являются фарфоровые плитки из Изника.

Историческая мечеть расположена в центре многолюдного района Эминоню на уклонной дороге, соединияющей Рынок Узун с побережьем. Мечеть построена на месте мечети Хаджи Халил на площади размером 40х40 м. В мечети имеется центральный купол диаметром 15,5 м., поддерживаемый окружающими его куполами и полукуполами малых размеров.

Во время пожара 1660 г. мечеть Рустам Паша потерпела повреждения, а во время землетрясения 1766 г. были разрушены минарет и купол мечети. Во время правления султана Мустафы II исторический памятник был отреставрирован, но минарет и купол после ремонта уже не были похожи на творения Мимар Синана.

Как и в мечети Михримах Султан, в мечети Рустам Паша также имеется стела. Во дворе находится восьмигранный шадырван. С трех сторон внутренний двор мечети окружен открытыми террасами.

Фарфоровые плиты из Изника, использованные для отделки расположенной на историческом полуострове мечети, придают ей красоту и неповторимость, что и привлекает посетителей.