İlk inşa tarihi kesin olarak bilinmeyen Erzurum Kalesi’nin M.S. 5. yüzyılın ilk yarısında Bizanslılar tarafından yaptırıldığı tahmin edilmektedir.
Tarih boyunca Assurlular, Sasaniler, Persler, Araplar, Romalılar ve Bizanslılar arasında sık sık el değiştiren Erzurum Kalesi, 11. yüzyılda Türklerin eline geçmiştir.
İç kalede Erzurum’daki ilk Türk-İslam eserlerinden Saltukoğulları dönemine ait Kale Mescidi ve Tepsi Minare bulunmaktadır. Erzurum Kalesi, bulunduğu tepenin üzerinde bir iç kale ile bunu çevreleyen dış kaleden oluşmaktadır. Bugün iç kale sağlam kalmış olmasına rağmen, şehri çevreleyen dış kale surları yok olmuştur. Günümüze ulaşan iç kalenin duvar kalınlıkları 2-2.5 m. arasında değişmekte olup, halen sekiz burcu ayakta durmaktadır.