Şeyhler Camii’nin vakfı olarak inşa edilen Şeyhler Hamamı'nın Şeyhler Camii ile aynı tarihlerde (1720) yaptırıldığı tahmin edilmektedir. 

Şeyhler Hamamı mimari özellik açısından klasik Osmanlı hamam planına sahiptir. Bu hamam Erzurum’da bulunan hamamlar arasında inşa edildiği dönemdeki özelliklerini korumayı başarmış en güzel örneklerden biridir. Hamam; soyunmalık, külhan, ılıklık ve sıcaklık bölümlerinden oluşmaktadır. Yapının doğusunda Külhan Baba’ya ait bir mezar bulunmaktadır. Külhan Baba veya Külhani Baba döneminin en önemli sofilerinden biri olarak bilinmektedir. Hamamın külhan bölümünde kalması sebebiyle ona bu ismin verildiğine inanılmaktadır. Külhan Baba’nın mezarının bulunduğu ahşap tavanlı kısımdan soyunmalık bölümüne geçilmektedir. Soyunmalık bölümü kare olarak planlanmış ve üzeri tromplar üzerine yerleştirilmiş bir kubbe ile kapatılmıştır. Orta kısmında havuz bulunan soyunmalık bölümünün zemini taş ile döşenmiştir. Soyunmalık bölümünün batısında bulunan bir kapı ile ılıklık bölümüne ulaşılmaktadır. Ilıklık bölümü dikdörtgen bir yapıya sahiptir ve güneyinde üzerleri tonoz ile kapatılmış tuvaletler bulunmaktadır. Ilıklık bölümünün batısındaki bir kapı aracılığıyla sıcaklık bölümüne ulaşılmaktadır. Sıcaklık bölümü dört eyvanlı ve dört köşe hücreli olarak planlanmıştır. Ortası kubbe ile kapatılan sıcaklık bölümünün kubbesinin altında sekizgen bir göbek taşı bulunmaktadır. Bu bölümün köşelerine sekizgen şekle sahip ve kubbeli halvet odaları yerleştirilmiştir. Sıcaklık bölümünün batısında ise hamamın su deposu ve külhan bölümleri bulunmaktadır.

Şeyhler Hamamının inşasında farklı malzemeler kullanılmıştır. Beden duvarlarında moloz ve kesme taş birlikte kullanılırken, üst örtüsünde ise tuğla malzeme tercih edilmiştir.