Kırkçeşme Hamamı, İç Kale’nin kuzey yamacında Ayaz Paşa Camii’nin yakınında yer almaktadır. Yapı üzerinde herhangi bir kitabeye rastlanmamıştır. Bu yüzden inşa edildiği tarih kesin olarak bilinmemektedir. Fakat mimari plan ve özellikleri incelendiğinde hamamın XVI. yüzyılın sonunda veya XVII. yüzyılın başında inşa edildiği tahmin edilmektedir. İbrahim Hakkı Konyalı eserinde Kırkçeşme Hamamı’nın Rüstem Paşa’nın hayır eserlerinden biri olduğunu ifade etmiştir. 

Kırkçeşme Hamamı; soyunmalık, ılıklık, sıcaklık ve külhan bölümlerinden oluşmaktadır. Aynı zamanda hamamın kuzey cephesinin bitişiğinde kadınlara özel hazırlanmış bir bölüm daha bulunmaktadır. Yapının batı cephesinde açılan bir kapıyla soyunmalık bölümüne girilmektedir. Soyunmalık bölümünde bazalt taşından yapılmış fıskiyeli bir havuz, bu havuzun önünde de suyun aktığı bir kurun (oluk) bulunmaktadır. Hamamın ılıklık bölümü kare planlıdır ve üzeri kubbe ile kapatılmıştır. Bu bölümün ortasında bir de şadırvana yer verilmiştir. Sıcaklık kısmı hamamda orijinalliğini koruyan bölümdür. Bu bölümün planına bakıldığında klasik Osmanlı hamam planlarıyla aynı özelliklere sahip olduğu görülmektedir. Sıcaklık bölümü ortada kubbeli bir mekân ve sivri kemerli dört eyvandan oluşmaktadır. Haç planlı olarak inşa edilen yapının dört köşesine üzerleri kubbeyle kapatılmış dört tane halvet hücresi yerleştirilmiştir. Ortadaki kubbenin altında ise bir göbek taşı bulunmaktadır. Göbek taşının çevresine üç adet yıkanma yeri ve yirmi bir adet kurna yerleştirilmiştir. Bu kurnalardan en fazla dikkat çekeni “gelin kurnası” isimli olanıdır. Hamamın iç kısmı çok aydınlıktır. Çünkü yapının ana kubbesi üzerine yıldız şeklinde pencereler yerleştirilmiştir. Bu pencereler sayesinde hamamın içi rahatlıkla aydınlatılmaktadır. Hamamın külhan bölümü sıcaklık bölümünün güney cephesiyle bitişiktir. Genellikle hamamların altında bulunan bir bölme olan külhan bölümünde hamamı ısıtmak için kullanılan büyük bir kazan vardır. 

Kırkçeşme Hamamı suyunu Erzurum Kalesi’nin altından çıkan ve kırk farklı çeşmeye dağılan sudan almaktadır. Hamamın inşasında moloz ve kesme taş birlikte kullanılmıştır. Yapı tarihsel süreç içerisinde pek çok kez onarımdan geçmiş ve böylece günümüze kadar ulaşabilmiştir.