Medrese, Şemsi Paşa semtinde ve bu isimle anılan camiin kuzey ve batı tarafında olup 'L' şeklindedir. Mimar Sinan tarafından, Şemsi Ahmet Paşa adına, 988 (1580) tarihinde, türbe ve cami ile beraber yapılmıştır. Kubbeli oniki hücre, bir darü'l-kurrası (dershane) olan bu güzel yapı bir sıra kesme taş ve üç sıra tuğla hatıllı olarak inşa olunmuştur. Hücrelerin önünde, onsekiz mermer sütunun taşıdığı, üzeri kubbeli olmayan bir revak vardır. Sütunlar birbirine sivri kemerlerle bağlanmışsa da medrese hücrelerinin duvarları ile bir kemer bağlantısı yoktur. Sütun başlıkları baklavalıdır. Revaklarda yeşil ve siyah porŞr gibi sütunlar da kullanılmıştır. Külliyenin onarımına başlanırken, Üsküdar İskele Meydanı'ndaki saatin altında yeşil bir sütunun bulunup cami avlusuna nakledildiği ve bunun benzerinin de, o tarihte vapur iskelesinin yanında bulunan, itfaiye binasında görülüp aynı yere taşındığı söylentisini dikkate alırsak revaklarda kullanılan değişik sütunların mahiyeti kolaylıkla anlaşılır. Bir rivayete göre de, bu sütunlar camiin içindeki müezzin mahŞline aittir. Medrese hücreleri 2.95 x 2.95 m. Boyutlarında olup duvar kalınlıkları 0.80 m.'dir. Hücrelerin her birinin içinde bir veya iki niş ve bir ocak vardır. Duvarlara altlı üstlü ikişer pencere açılmıştır. Köşe odalarında pencere sayısı daha fazladır. Hücrelerin ortasında 7x7 m. ebadında medresenin darü'lkurrası bulunmaktadır. Burada altlı üstlü 16 pencere vardır. Sağır kubbesi sekiz yüzlü bir kasnak üzerine oturtulmuştur. Söveleri beyaz, kemeri beyaz mermer ile puding taşının alternatif olarak sıralanmasıyla meydana gelmiş olan kapısının takında ve bir çerçeve içinde bir âyet vardır. Bu medreseye Tuhfetü'l-Mimarîn 'Tekye'; Tezkiretü'l-Ebniye 'Medrese' demektedir. Medrese, Şemsi Paşa'nın vefatından kısa bir zaman sonra tekke haline getirilmiştir. Hadîka yazarı, eserinin 98. sayfasında Vişnezâde Mescidi bahsini yazarken: "Bir başka Vişnezâde Şeyh Mehmet Efendi dahi vardır ki, ibtida Şemsi Ahmet Paşa Zaviyesi'ne şeyh olan eş-şeyh Hızır Efendi, İstanbul'da vaki Mehmet Ağa Zaviyesi'ne naklolundukta, adı geçen Vişnezâde onun yerine şeyh olmuştur. Bunun tarih-i vefatı 1010 (1601-2) senesinde vuku bulmuştur." diyor ve Mehmet Ağa Camii'ni yazarken de bu Hızır Efendi'den: "Mehmet Ağa Zaviyesi'nin birinci şeyhi, Yayabaşızâde Hızır Efendi ibn-i İlyas Efendi'dir ki, Üsküdar'da Şemsi Ahmet Paşa Zaviyesi'nin şeyhi iken bu zaviyeye naklolundu. Sonra, Rikab-ı Hümâyûn ile bulunan meşayih ile beraber Eğri Seferi'ne azimet edip tabur muharebesinde şehid olarak cesedi Tatarpazarı' na (Bulgaristan'da) nakil ve anda Tülbentçi Camii'nde defnolundu. Sene, 1005 (1596)." diye bahsetmektedir. Şemsi Paşa Tekkesi'nin diğer bir şeyhi de Nefes Ambarı lâkabıyla bilinen Şeyh Osman Efendi'dir. Kendisi, Kayseri'den 1044 (1634)'te Abaza Şeyhi Abdürrahim Efendi ile İstanbul'a gelmiştir. Abdürrahim Efendi 1047 (1637-38)'de idam edilerek Üsküdar Mihrimah Sultan Camii hazîresine gömülmüştür ki, kabir taşı bugün de mevcuttur. Medresenin hangi tarihe kadar tekke durumunu muhafaza ettiği şimdilik belli değildir. 1890 tarihlerinde yazılan Mecmua-yı Tekaya'da bu tekkenin ismi geçmediğine göre, tekke bilinmeyen bir tarihte faaliyetini durdurmuş olmalıdır. Hadîka yazarı, eserini 1182 (1768) yıllarında yazdığı ve bu medreseden hâlâ tekke diye bahsettiğine göre, tekke, ayinlerini bu tarihlerde de yapıyor olmalıdır. Medrese, 1894 zelzelesinde çok zarar görmüş ve oturulamaz hale düşmüştür. Bu halde iken, 1940 tarihinde Vakıfça onarılmıştır. Aslına uygun olarak gerçekleştirilen bu restorasyon, Y. Mimar Süreyya Yücel Bey tarafından yapılmıştır. Medrese, 1953 tarihinde de Şemsi Paşa Halk Kütüphanesi adı ile tekrar hizmete açılmıştır.