Melik Mehmet Gazi Medresesi’nin Anadolu’nun ilk medresesi olma ihtimali, tarihî kaynaklara dayanmaktadır. Bu medresenin, Melik Mehmet Gazi’nin tahta çıktığı 1134 yılı ile vefat ettiği 1143 yılı arasındaki dönemde inşa edildiği kabul edilmektedir. Bu durumda, Melik Mehmet Gazi Medresesi, Yağıbasan Medresesi’nden yaklaşık 10 yıl daha önce inşa edilmiş olup, Anadolu’nun ilk medresesi unvanını taşımaktadır. Melik Mehmet Gazi Medresesi, Danişmendli Melik Mehmet Gazi tarafından inşa ettirilmiştir. Kesin yapım tarihi hakkında net bir bilgi bulunmamakla birlikte, Melik Mehmet Gazi’nin Kayseri’yi başkent yapması ve imar faaliyetlerine hız vermesi döneminde inşa edildiği bilinmektedir. Bu süreçte medreseye, ünlü Hanefi fakih ve Kayseri’nin ilk kadısı olan Abdülmecid b. İsmail el-Herevi müderris olarak atanmıştır. Medrese, I. Gıyaseddin Keyhüsrev döneminde, Melik Mehmet Gazi’nin yeğeni Muzafferü’d-din Mahmud bin Yağıbasan tarafından 1205/6 (H. 602) yılında onarım görmüştür.
Yunan filolog ve paleograf Grigorios Nikolaou Bernardakis, 1907 civarında Kayseri’nin topografyası üzerine yürüttüğü çalışma sırasında bu medreseden söz etmiştir. Bernardakis’in tespitleri, 1908 yılında yayımlanan “Notes sur la topographie de Césarée de Cappadoce” başlıklı makalesinde yer almıştır. Ayrıca “Plan de Césarée de Cappadoce” adlı haritada medrese cami ile beraber 12 numara ile gösterilmiştir. Bernardakis, Cami-i Kebir ya da Ulu Cami’yi, güneyinde ona bitişik olan medresesiyle birlikte ele almıştır. Ona göre bu cami, Selçuklular tarafından bir Hristiyan kilisesinin bulunduğu yerde, bu yapıların malzemeleri kullanılarak inşa edilmiştir. Camide, 5. yüzyıla ait akantus yapraklarıyla süslü güzel sütun başlıkları vardır. Medresede ise haçlarla süslenmiş çok eski başlıklara sahip sütunlar bulunmaktadır. Bernardakis’in aktardığına göre bu yer, o dönemde Müslümanlar tarafından hâlâ “Keşişlik” olarak adlandırılmaktaydı, bu ad “manastır” anlamına gelmektedir.
1922 yılına kadar, Melik Mehmet Gazi Medresesi, Kayseri’de eğitim ve öğretim faaliyetlerinin devam ettiği dört medreseden biri olarak faaliyetteydi. Bu dönemde medresede 15 öğrenci bulunduğu bilgisi kayıt altına alınmıştır. 1934 yılında medresenin hala ayakta olduğu belirtilmiştir. 1966 yılında, Kayseri Belediyesi tarafından medresenin son kalıntıları da tamamen yok edilmiştir. Bu yok ediliş sürecinde, yapının temelleri üzerine tuvalet inşa edilmiş ve tarihî izler kesme taşlarla kaplanarak silinmiştir. Günümüze ulaşan tek yapı, caminin güneyinde yer alan ve medresenin 12 odasının arasındaki Melik Mehmet Gazi Türbesi’dir. Son yıllarda Mustafa Cingil ve ekibi tarafından yapılan çalışmalarda, medresenin tam yeri tespit edilmiş ve Kayseri Ulu Camii’nin güneyinde, Melik Mehmet Gazi Türbesi’ni de içine alacak şekilde bulunduğu ortaya konmuştur. Taç kapısının batı cephesinde yer aldığı belirlenmiştir.
