Erzurum İç Kale’de Ulu Cami Tebriz Kapı semtinde, kalenin kuzey duvarının bir burcuna bitişik olan Kale Camisi’nin kitabesi günümüze gelememiştir. Bu cami kale muhafızları için XII.yüzyılda Saltukoğlu İnanç Biygu Alp Tuğrul tarafından yaptırılmıştır. Bazı kaynaklarda kale ile birlikte 1154’te İzeddin Saltuk tarafından yaptırıldığı yazılıdır. Yine bazı kaynaklarda da günümüze gelememiş olan kitabesinde 1179-1180 yılında Ebü’l-Feth Melik Muhammed tarafından yaptırıldığı yazılıdır.

Camiye İç Kale meydanındaki bir kapıdan girilmektedir. Kıble duvarı, kale duvarı ile ortak olan bu kapı kalenin avlusuna da açılmaktadır. Giriş kapısının ve yanlarındaki pencerelerin üzerinde bezemeler bulunmaktadır. Cami kesme taştan yapılmış olup, dikdörtgen planlıdır. İç mekan mihraba paralel iki sahından meydana gelmiştir. Girişin üzeri çapraz tonoz ile örtülüdür. Mihrabın önünde mukarnaslı kasnaklar üzerine oturmuş bir kubbesi vardır. Bunun dışında kalan bölümler de beşik tonozlarla örtülmüştür. Yapının ön kısmı toprak damlıdır. Mihrap önü ise konik bir külah ile örtülmüştür. Bu külahın gövdesi silindir şeklinde ve kalker taşından yapılmıştır. Gövdesi ikişer kabartma silme ile 16 bölüme ayrılmıştır.

İbadet mekanı 8.75x9.80 m. ölçüsündedir. İbadet mekanında ortada L şeklinde iki ayak burasını ikiye ayırmaktadır. Ön kısmın iki yanında yüksek birer sivri tonoz, ortasında ise bir çapraz tonoz bulunur. Mihrap önü ortadaki iki ayağın üzerinde bulunan sivri kemerlerle, yanlarda da iki sivri tonoz ile takviye edilmiştir. Kuzeydeki üç, kubbe eteğindeki dört pencere ile aydınlatılmıştır. Kabartma süslerle bezeli olan mihrap yarım yuvarlak olup yanındaki kalenin burcu içerisine yerleştirilmiştir. Üzerindeki mermerden kırık kitabenin cami ile bir bağlantısı bulunmamaktadır.

Caminin yanındaki saat kulesi aynı zamanda minare olarak kullanılmıştır. Caminin etrafı kalenin depoları ile kuşatılmıştır.