Giriş kapısı üzerinde yer alan kitabeye göre I. Sultan Mahmut döneminde 1738 yılında Narmanlı Hacı Yusuf Efendi tarafından yaptırılmıştır. Erzurum’un önemli ibadet merkezlerinden biri olan Narmanlı Camii Osmanlı mimarisine sahip tarihi camilerden bir tanesidir. Narmanlı Camii ortası büyük yanları küçük beş kubbeden oluşuyor. Cami iç kısımda dört köşede tromplar üzerine oturan kubbesi ve dışarıya 16 kenarlı bir kasnakla yansımaktadır. Kare planlı olarak tasarlanan caminin yapımında düzgün kesme taş kullanılmıştır. Caminin güneyinde mukarnas süslemeli sade bir mihrap ve kuzeyinde sekiz destek üzerinde oturan ahşap kadınlar mahfili yer almaktadır. Caminin girişinde kubbeyle örtülü beş bölümlü son cemaat yerinin bulunması ve Erzurum’da bulunan tek kubbeli diğer camilere göre daha büyük çapta bir kubbeye sahip olması bu tarihi yapının önemini artırmaktadır Narmanlı Camii çevresinde haziresi bulunmaktadır. Yapının önünde duvarla çevrili küçük mezar alanında Narmanlı Hacı Yusuf ve ailesine ait olduğu tahmin edilen mezar yapıları bulunmaktadır.

Vakıflar Bölge Müdürlüğü tarafından 2015-2016 yılları arasında yapılan restorasyon çalışması sonucunda daha önceki dönemlerde toprak kayması nedeniyle kaybolan, yapının kuzey ve güney cephelerinde yer alan etrafı çevrili olan haziresinde 52 mezar yapısından 23 tanesi gün yüzüne çıkarılmıştır. Bu mezar yapılarının Erzurum eski valilerinden Siyavuş Paşa başta olmak üzere şehrin diğer önde gelenlerinden Zeliha Hatun, Lütfullah Efendi, Hacı Salih Çelebi, Mülazım Osman Ağa, Salih Efendi, Musa Paşa, Şeyh Şamil’in silah arkadaşı Hasbulat Bey’e ait olduğu tespit edilmiştir. Bunun yanı sıra restorasyon öncesi beyaz boya ile boyanan ahşap mahfilde yağlı boya raspası yapılarak altındaki esas dokuya ulaşıldı ve XVIII. yüzyılda yaygın olarak kullanılan dekorasyonlardan biri olan kalemişi ile yapılan bitkisel bezemeler ortaya çıkarılmıştır. Bu bezemelerde siyah, kırmızı ve krem rengi kullanıldı. Bir kısmı tahrip olmasına rağmen, lale, karanfil, sümbül anemon veya gül ve servi bezemelerde kullanılan çiçek ve ağaç motifleri tespit edilmiştir.

Eşsiz mimari özellikleri ile dikkat çeken Narmanlı Camii, Erzurum Gürcü Kapı Camii’de olduğu gibi geniş avlusu olması nedeniyle Erzurum şehrinin cenazeleri sürekli olarak buradan kaldırılmakta ve bu nedenle yerel halk tarafından Hüzünlü Cami olarak da adlandırılmaktadır.

Narmanlı Camii’nin yapımı halk arasında bir rivayete dayanmaktadır. Rivayete göre; Narmanlı Hacı Yusuf adıyla bilinen kişi akşam saatlerinde yanında hizmetkârlarıyla birlikte şehir içinde bir yere gider. Hizmetkârdan biri Narmanlı Hacı Yusuf’un önünde kandille ilerlerken Hacı Yusuf’un yolunu aydınlatır. Daha sonra bir şekilde Hacı Yusuf’un öne geçmesi ile hizmetkâr arkada kalır. Hacı Yusuf ilerlerken ayağı tümseğe takılıp yere düşer. Bunun üzerine endişelenen hizmetkâr “Arkada olan ışığın kimseye faydası olmaz, herkes ışığını kendi götürmeli’’ diye bir cümle kurar. Bu cümleyi çok anlamlı bulan Narmanlı Hacı Yusuf malının mülkünün bir kısmını fakire fukaraya verir. Hizmetkârlarını azat eder ve bir cami yaptırmaya karar verir. İlk zamanlarda Narmanlı Camii derme çatma olarak yapıldı. Bu durumun farkına varan dönemin valisi bu yapıdan iyi han olur diye söylediği zaman Hacı Yusuf bu duruma çok üzüldü ve bu camiyi yaptırmak için çok fazla para harcadığını belirterek bunun nedenini sordu. Vali bu yapının ısıtılmasının zor olacağını belirtti. Bunun üzerine Hacı Yusuf daha fazla para harcayarak bugün günümüze ulaşan camiyi yaptırmıştır.

Narmanlı Cami, Erzurum'un Yakutiye ilçesinin Tebrizkapı semtinde, Narmanlı Mahallesi'nde ve Çifte Minareli Medrese’nin doğusunda yer almaktadır. Yapının tarihi girişi kapısı üzerinde bulunan mermer kitabe talik hatlı olup   0.40 x 0.50 metre ölçülerindedir.  Dört satırlık kitabeye göre yapı 1151 H.-1738 M. yılında Sultan I. Mahmud (1730-1754) döneminde Narmanlı Hacı Yusuf Efendi tarafından inşa ettirilmiştir. Kitabe metni şöyledir: 

Narmanî Hacı Yusuf cami’i itdi bina. 

Ola Makbul-i Huda idüb gavs-ı Hur-i cinan 

Fikr tarihin iderken Veysiya Hâtıf dedi:

 Ma’bed-ecell-i ibadet secdegâh-i ârifîn

Caminin vakfiyesi ise inşasından çok sonra H.1189 / M.1775 yılında tescil ettirilmiştir. Bu vakfiye kaydına göre vakfın sahibi babası Salih’tir. Caminin önünde duvarlarla sınırlandırılmış hazirede Narmanlı Hacı Yusuf ve ailesine ait olduğu söylenen mezarlar yer alır. Caminin doğu ve güneyindeki mezarlarda ise devlet bünyesinde görev almış kişilerin, şehrin tanınmış simalarının ve yakınlarının kabirleri bulunmaktadır. Bu mezar yapılarının, Erzurum eski valilerinden Siyavuş Paşa başta olmak üzere Musa Paşa, Zeliha Hatun, Mülazım Osman Ağa, Lütfullah Efendi, Salih Efendi, Hacı Salih Çelebi ve Şeyh Şamil’in silah arkadaşı Hasbulat Bey’e ait olduğu tespit edilmiştir. Yine caminin yaklaşık 50 metre güneyinde de Ahibaba Türbesi yer alır. Ayrıca Narmanlı caminin kuzeybatı avlu duvarına konumlandırılmış, sivri kemerli, iki gözlü, tarihi bir çeşme bulunmaktadır.

Büyük boyutlu kesme taş malzeme ile inşa edilen kare planlı cami, tek kubbeli olup kubbe geçişleri tromplarla sağlanmıştır. Girişi kuzeyde olan yapının bu bölümünde, duvara bağımsız altı taş sütun tarafından taşınan beş gözlü son cemaat yeri bulunur. Son cemaat yerinin üzeri ortadaki yanlara göre daha büyük ele alınan beş kubbe ile kapatılmıştır. Kuzeybatı köşede ise beden duvarları üzerinden yükselen kesme taş malzemeli minare kare kaideli, silindirik gövdeli ve tek şerefelidir. Caminin doğu ve batı cephelerinde dikdörtgen formlu düz lentolu pencereler altta iki, üstte bir tane olup bu pencere sayısı güney ve kuzey cephede mihrap ve kapı kullanımdan dolayı altta iki adet olarak değerlendirilmiştir. Kuzey cephedeki pencereler diğer cephelerdeki pencerelerden farklı olup, burada Gümrük Camisi’nde olduğu gibi bu pencerelerin üzerinde sivri kemerli alınlıklara yer verilmiştir. Aynı zamanda yapının aydınlatmasına kubbenin oturduğu sekizgen kasnağın her yönüne açılan pencereler ve ana yönlerde değerlendirilen alçı şebekeli pencerelerde katkı sağlamaktadır. 

Kuzey cephede bulunan basık kemerli kapı, silmelerle oluşturulan dikdörtgen çerçeve içerisinde çift kademeli sivri kemerle oluşturulmuştur. Harime geçiş veren bu kapının karşında güney yönde iki yanda sütunceleri bulunan mukarnas kavsaralı mihrap ve hemen yanında yenilenmiş minber bulunur. Kuzeyinde ise sekiz ahşap desteğin taşıdığı kadınlar mahfili dikkat çeker. 

Mahfilin kalemişi süslemeleri XVI. yüzyıl klasik Osmanlı ve XVIII. yüzyıl geç dönem sanat üslubuyla yorumlanmış motiflerle bezenmiştir. Lale, gül, karanfil motifleri kemer aynalarında, sümbül ve menekşeler bahar dallarıyla sütunların mukarnas başlıklarında siyah tahrir uygulamarıyla kompoze edilmiştir. Kubbelerde görülen kalemişleri ise sıva üstü tekniğiyle son dönem uygulamalarıdır.

Narmanlı Camii'nin önünde bulunan geniş avlu, cenazelerin sıklıkla buradan kaldırılmasına olanak sağladığından halkın camiye Hüzünlü Cami olarak adlandırmasına neden olmuştur.