Esat Paşa Cami, Erzurum İç Kalesi’nin batısında, Tepsi Minare’ye (Saat Kulesi) yakın bir yerde inşa edilmiştir. Caminin giriş kapısının üzerinde bulunan Sultan Abdülmecit’in tuğrası ve Şair Cazim tarafından yazılmış olan beş satırlık bir mermer kitabe bulunmaktadır. Kitabeden elde edilen bilgilere göre, camiyi 1830-1836 yılları arasında Erzurum Valiliği yapmış olan Esat Muhlis Paşa inşa ettirerek Sultan II. Mahmud’a bağışlamıştır. Cami, 1851-1852 yılları arasında on sekiz aylık bir süreçte Erzurum Valisi olan Zarif Mustafa Paşa döneminde harap bir halde iken Paşa, Sultan Abdülmecid’e durumu iletmiş ve bunun üzerine Sultan, 1852 yılında camiyi İstanbul'daki Nur-i Osmaniye Camii'ni kıskandıracak bir şekilde onarımdan geçirtmiştir. Şair, bu caminin korunması hususunda Nakşibendi tarikatının şeyhi ve mürşidi olan Osman Efendi'yi işaret etmiştir (Konyalı 1960: 201). 

Camiyi yaptıran Erzurum Valisi Esat Muhlis Paşa, 1828-1829 Osmanlı-Rus Savaşı'ndan sonra bölge hakkında bilgi sahibi olmasından dolayı Erzurum Valiliğine atanmıştır. Sahip olduğu vezirlik rütbesine ilave olarak kendisine, olağanüstü durumlarda Erzurum valilerine verilen Şark Seraskerliği (Doğu Orduları Kumandanlığı) unvanı da verilmiştir (Şahin ve Subaşı 1995: 350). 1836 yılında, Erzurum-Van-Bayazıt sancaklarından oluşturulan ve yeni kurulan Erzurum Redîf-i Mansûre Müşirliği’ne atanmıştır (Çadırcı 1963: 71). Erzurum Valiliği yaptığı süreç içerisinde Nakşibendi Şeyhi Osman Efendi’ye karşı saygı ve muhabbet besleyen Esat Muhlis Paşa’ya, Osman Efendi’ye bağlı müritler tarafından bir cami yapılması için talepte bulunulmuştur. Bunun üzerine Sultan II. Mahmut’a bir yazı gönderen Esat Muhlis Paşa camiyi kendisinin yaptıracağını ve Sultan adına bağışlanacağını belirtmiştir. Ayrıca aynı yazıda Osman Efendi’ye Erzurum'un gümrük gelirlerinden de bir aylık bağlanmasını talep eden Paşa’nın bu arzı Padişah tarafından kabul edilmiş ve kendisine 300 kuruş maaş bağlanmıştır (Küçükuğurlu 2020: 94).

Caminin son cemaat yerinin sol tarafında içerisinde iki mezar bulunan bir türbe yer almaktadır. Bu mezarlardan biri 1866 yılında hayatını kaybetmiş olan Nakşibendi Şeyhi Osman Efendi’ye aittir. Mezar taşı üzerindeki metni edebi bir dil ile Şair Galib nazmetmiş ve Mısri yazmıştır (Konyalı 1960: 202). 

Cami, düzenli ve yüksek kaliteli kesme taş işçiliği ile öne çıkmaktadır. Ahşap destekli düz bir tavana sahip olan yapı, dikdörtgen bir plana sahiptir. Girişin üzerinde bir mahfil bulunmaktadır. Dört ana sütun üzerine inşa edilen cami, tarihi yapısına sadık kalınarak Vakıflar Genel Müdürlüğü tarafından yenilenmiş ve tekrar kullanıma sunulmuştur (Tunçay ve Yavuz 2023: 480).

Caminin doğu ve batı cephelerinde ise üçer, kuzey ve güney cephelerinde ikişer pencere bulunmaktadır. Günümüzde üzeri kapatılan son cemaat yeri, altı adet ahşap sütun üzerine inşa edilmiş ve eğimli bir çatı ile örtülmüştür. Cami minaresi, kuzeybatıda konumlandırılmakla birlikte zemini kare kaideli iken gövdesi silindirik bir şekilde yapılmıştır. Ayrıca minarenin pabuç bölümü küp şeklinde olmakla birlikte bu yapısından dolayı Erzurum camileri arasında benzersizdir (Erzurum İl Kültür ve Turizm Müdürlüğü 2024). 

Bununla birlikte Caminin güney cephesinde bir mezarlık bulunmaktadır. Mezarlıkta çok sayıda din alimi, askeri görevliler, müritler ve kadınların mezarları bulunmaktadır. Mezar taşları üzerinde hem Türk mitolojisinin hem de İslami motiflerin görülebileceği değerli işlemeler bulunmakta ve kültürel miras açısından da camiye ayrı bir değer katmaktadır (Kayserili 2015).

Esat Paşa Cami, Gayrimenkul Eski Eserler ve Anıtlar Yüksek Kurulu tarafından 13.11.1976 tarihli ve A.188 sayılı tescil kararı ile koruma altına alınmıştır. Zaman içerisinde hem dış bahçe duvarlarının hem de cami minaresinin doğal yapısında bozulmalar tespit edilmesinden dolayı da 2017 yılında restorasyon yapılmış ve ardından tekrar ibadete açılmıştır.