U vakufnami je do u detalje odredio osnove budućeg rada Medrese, čiji će profesori biti birani po strogom kriteriju, na temelju stručnosti, pedagoškog iskustva i ljudskih kvaliteta.
Originalno nazvana Seldžuklija, po Gazi Husrev-begovoj majci Seldžuci, osmanskoj princezi, Medresa je kasnije zbog svojih olovnih kupola, od kojih su u ratna vremena lijevani meci (tur. kuršumi), prozvana Kuršumlija.
Dubrovački majstori i domaći neimari
Izgradili su je dubrovački majstori i domaći neimari u srcu Stare sarajevske čaršije, preko puta Gazi Husrev-begove džamije, po projektu tada vodećeg arhitekte Osmanskog carstva, Perzijanca Adžema Esira Alija.
Osmišljena je kao građevina sa 12 učeničkih soba poredanih u polukrug, između kojih je bila centralno postavljena dershana (predavaonica).
Kutubhana (biblioteka) bila je smještena uz Begovu džamiju, dok je uz Medresu sagrađen i Hanikah, centar za izučavanje tesavvufa, islamskog misticizma.
Za vladavine Osmanskog carstva Medresa je bila viša obrazovno-odgojna ustanova, dok u prvim godinama austrougarske uprave postaje usko specijalizirana vjerska škola, jer tada sa radom otpočinju i muslimanske škole sa svjetovnim programom – Šerijatsko-sudačka i Učiteljska škola.
Tokom 1897. je preseljena u Đulagin dvor, palatu sagrađenu na mjestu nekadašnjeg hana, a 1913. je spojena sa Učiteljskom školom, koja je ugašena 1920. godine. Naredne, 1921. godine Kuršumlija i Hanikah ujedinjeni su u Gazi Husrev-begovu medresu (GHM), a 1933. je otvoreno i žensko odjeljenje Medrese.
Gazi Husrev-begova medresa je 1945. preseljena u prostor u ulici Hamdije Kreševljakovića, gdje učenici 1972. organizuju dvomjesečni štrajk u želji da dobiju kvalitetniji i priznat obrazovni program.
U Đulagin dvor se Medresa vraća 1977. godine, a sprva u tom prostoru djeluje skupa sa novootvorenim Islamskim teološkim fakultetom (danas Fakultet islamskih nauka).
U vremenu nakon Drugog svjetskog rata Gazi Husrev-begova medresa i Alauddin medresa u Prištini su dugo bile jedine islamsko-obrazovne ustanove u čitavoj bivšoj Jugoslaviji.
Muzej i Hanikah
Muško odjeljenje GHM-a danas djeluje u Saračima, u bivšem Đulaginom dvoru, dok je žensko smješteno u ulici Hamdije Kreševljakovića. U originalnoj zgradi Medrese, Kuršumliji, danas djeluje Gazi Husrev-begov muzej, a Hanikah služi za realizaciju dijela aktivnosti Medrese, te kao izložbeni prostor.
Reformom obrazovanja iz 2004. godine počinje djelovati kao Javna ustanova srednja islamska vjerska škola sa internatom, sa 70 posto općeg obrazovnog sadržaja po uzoru na program gimnazije i 30 posto vjerskog sadržaja, pa su danas njenim svršenicima otvorena vrata gotovo svih domaćih i mnogih fakulteta u svijetu.
