Şeyhler Medresesi, Şeyhler Mahallesi’nde cami, medrese, hamam, çeşme ve türbeden oluşan Erzurum’daki Osmanlı dönemi külliyesinin bir parçasıdır. Arşiv kayıtlarına göre Erzurum’da Osmanlı döneminde inşa edilmiş yirmi üç medrese yapısı tespit edilmiş, bunlardan sadece üçü günümüze ulaşmış, bunlardan biri de Şeyhler medresesidir. Medrese giriş kapısı üzerinde mermer üzerine dört satırlık sülüs harflerle yazılmış kitabesine göre, Müftü Şeyh Mustafa Efendi tarafından 1174 H.-1760 M. yılında inşa ettirilmiştir. Kitabe metni şu şekildedir:

Şeyhler Medresesi açık avlulu, tek katlı ve dikdörtgen planlı bir Osmanlı medresesidir. Medreseye giriş doğu cephesinde açılan, sade bir kapı ile sağlanmaktadır. Medresede; revaksız bir avlu etrafında sıralanan güneyde ve batıda üç, kuzey dört, doğuda iki olmak üzere toplam on iki oda bulunmaktadır. Farklı ölçülerde ele alınan beşik tonozla örtülen odaların doğu, batı ve güney cepheleri avluya iki mazgal pencere ile açılmaktadır. Dikdörtgen odaların girişleri alçak tutulmuş, düz atkı taşlı ve sade bir mimariye sahiptir. Dışa kapalı içe dönük medresede avluya bakan cephe son derece sade olarak düzenlenmiştir. Medresenin kuzeybatı köşe odasının batı duvarında sonradan dikdörtgen bir pencere açılmıştır. Odaların bazılarının içerisinde iki, bazılarında dört niş yer almaktadır. Bugün yalnız kuzeybatı köşe odasının üzeri düz tavan şeklindedir. Medresenin dış cephelerinde düzgün kesme taş ve moloz taş, odaların avluya bakan cephelerinde düzgün kesme taş malzeme kullanılmıştır.