Ulu Cami’nin doğusuna bitişik olan bu medreseden Evliya Çelebi, “Kızıl Cami Medresesi” olarak bahsetmektedir. Günümüze ulaşmamış olan bu medresenin kuzey duvarı ve bu duvar üzerinde yer alan kitabeli kapısı ayaktadır. Eyyubi neshisi ile yazılmış olan kitabede medresenin H.587 (M1191) tarihinde Selahattin Eyyubi tarafından yaptırıldığı yazılıdır.
Daha sonra Osmanlı döneminde bu medresenin yerine bugün ayakta olan Nakibzade Medresesi inşa edilmiştir.