Büyük bir bahçenin içinde olduğu bilinen bu saray, Salacak İskelesi ile Ayazma İskelesi arasında idi. Naimâ Mustafa Efendi ünlü tarihinde: "Kapıcılar Kethüdası Abdullah Ağa, Padişah tarafından gelip sadrazamlık mührünü İbrahim Paşa'dan alıp Hadım Paşa'ya teslim etti. İbrahim Paşa ferman mucibince Üsküdar'da Salacak İskelesi yakınında olan bahçesinde oturdu." denilmektedir. İbrahim Paşa, 3 Aralık 1597 tarihinde sadaretten uzaklaştırıldığına göre saray, daha evvel yapılmış demektir. Paşa, 992 (1584) tarihinden beri III. Murat'ın kızı Ayşe Sultan ile evli bulunuyordu. İhtimal sarayını bu evlilik sırasında yaptırmıştır. O sırada Mısır Valisi idi. Evliya Çelebi'nin muasırı olan Eremya Çelebi (1637-1695) İstanbul Tarihi, adlı eserinde bu saraydan bahsetmiştir. Buna göre "Ayşe Sultan Bahçesi'nin" önünde bu saraya ait olduğu sanılan "bir Taş Liman" vardı. "Onun karşısında bir adayı andıran Kızkulesi bulunmakta" idi. Mihrimah Sultan'ın kızı Ayşe Sultan'ın da bu civarda bir sarayı vardı ve bu sırada hayatta idi. Üsküdar'da başka bir Ayşe Sultan Sarayı daha vardı ki bu, Zeynep-Kâmil Hastahanesi civarında bulunuyordu. Bu üçüncü Ayşe Sultan 1656 senesinde vefat etmiştir. İnciciyan da eserinde Ayşe Sultan Bahçesinden bahsetmiştir. Sarayın ilk sahibi olan İbrahim Paşa'nın üç sadrazamlığı ve bir kaptan-ı deryalığı vardır. Son defa 6 Ocak 1599'da sadaret mevkiine getirilmiş ve bu görevde iken 9 Muharrem 1010 (10 Temmuz 1601)'de Belgrad'daki ordu karargâhında vefat etmiştir. Cenazesi İstanbul'a getirilerek Şehzade Camii avlusundaki türbesine gömüldü. Yanında oğlu ile kızı medfundur. Ayşe Sultan, III. Murat'ın meşhur Safiye Sultan'dan doğma kızıdır. İbrahim Paşa'nın vefatı üzerine 5 Nisan 1602'de Yemişçi Hasan Paşa ile evlendirildi. Fakat 4 Aralık 1603'te Paşa'nın idamıyla tekrar dul kaldı. Ve kısa bir müddet sonra 26 Zilhicce 1013 (15 Mayıs 1604)'te vefat ederek babasının türbesine gömüldü. İbrahim Paşa'nın vefatı üzerine Ayşe Sultan'ın uhdesine geçen sarayda kısa bir müddet için de olsa Yemişçi Hasan Paşa'nın oturduğu anlaşılmaktadır. Ayşe Sultan'ın İstanbul'daki sarayından alınarak Sütlüce'deki 'hadîka-i hassa'dan Handan Ağa Bahçesi'nde idam edilen Hasan Paşa, Üsküdar'da Miskinler Tekkesi civarına gömülmüştür. Mezarı kaybolmuştur. Yemişçi Hasan Paşa'nın İstavroz'da (Beylerbeyi) büyük bir bahçesi ve köşkü vardı.