Ana giriş kapısında yer alan kitabesine göre II. Selim’in paşalarından Kuyucu Murat Paşa tarafından Erzurum’da sadrazamlık görevi sırasında, İlhanlılardan kalma harap cami temelleri üzerine 1573 yılında yaptırılmıştır. Bir külliye biçiminde tanzim edilen yapı kare planlı olup, günümüzde Erzurum’un en önemli ibadet mekânları ve tarihi yapıları arasında yer almaktadır. Murat Paşa Camii, Lala Paşa Camii’nden sonra Erzurum’da bulunan ikinci Klasik dönem Osmanlı mimarisine ait cami olmakla beraber, yapı, plan ve mimari bakımdan kendisinden sonra inşa edilen tek kubbeli camilere bir örnek model oluşturan, hemen bitişiğinde bulunan Ana Hatun Türbesi ve Ahmediye Medresesi ile bir bütünlük oluşturmaktadır.

Osmanlı İmparatorluğu döneminden günümüze kadar gelen Murat Paşa Camii tarihsel süreç içerisinde birkaç defa onarım geçirmesine rağmen, bugün hala orijinalliğini korumaktadır. Kare planlı olarak tasarlanan Murat Paşa Camii’nin ibadet mekânını köşelerde tromplara oturan mukarnas süslemeli altı sütunun taşıdığı merkezi bir kubbe örtmektedir. Merkezi kubbe kasnağında 12 pencere ve altında bir ayet işlemesi yer almaktadır. Kubbe tromp ve kemerleri XIX. yüzyılda alçı üzerine yağlı boya kullanılarak Avrupa üslubunda çiçek ve yaprak motifleri ile bezelidir. Bunun yanı sıra, caminin mihrabı taştan ve mukarnas süslemeli olup, dikdörtgen bir niş içerisindedir. Murat Paşa Camii’nin ahşap kapısı, minberi ve pencere kapakları Osmanlı dönemi ahşap işçiliğinin en güzel örneklerini yansıtmaktadır. Caminin son cemaat yeri birbirlerine yuvarlak kemerlerle bağlı olan altı sütunun taşıdığı beş kubbe ile örtülüdür.

Erzurum’un önemli kültür miraslarından biri olan Murat Paşa Camii’nin minaresi yapıdan bağımsız olarak tek şerefeli, yapının sağ tarafında sekizgen kaide üzerine yükselmekte ve doğusunda bulunan Ahmediye Medresesi ile ortak olarak kullanılmaktadır. Günümüzde kullanılan minare daha yüksek ve kalın gövdeli olan eski minarenin yerine yakın bir dönemde inşa edilmiştir. Caminin son cemaat yeri üç kubbe ile örtülüdür. Son cemaat yeri ile iç mekânı örten tek kubbeden ibaret caminin duvar yüzeyleri kesme taştan, taç kapı ve pervazları ise kırmızı kamber taşındandır. Murat Paşa Camii Osmanlı döneminde erken tarihli yapılan camilerde görülen sadeliğe sahip olmakla beraber, cami ve minaresinin kesme taştan inşa edilmesiyle diğer Erzurum camileriyle ortak özellik göstermektedir.

Murat Paşa Camii halk arasında efsanevi cami olarak adlandırılmaktadır. Cami hakkında çeşitli rivayetler bulunmaktadır. Bir rivayete göre, caminin inşaatı devam ederken, Murat Paşa bir işçinin taşları yukarıya çıkarıp, duvara koymadan tekrar aşağıya indirdiğini görür. Murat Paşa işçiye ne yaptığını sorduğunda, işçi su olmadığından yıkanamadığını, abdest alamadığını ve bu haliyle bir mabede taş koyamayacağını ifade eder. Murat Paşa bu durumun önemini hemen kavrar ve cami inşaatını durdurarak, caminin hemen yanına bir hamam yapısının yapılmasını ister. Hamamın inşası bittikten sonra cami inşaatına devam edilir. Cami inşaatında çalışan işçilerin çalışmaya başlamadan önce hamamda yıkandıkları rivayet edilmektedir. Bir başka rivayete göre ise Murat Paşa Camii’yi yaptırırken rüyasında Ahmediye Medresesi’ni yaptıran Ahmet Bey’i görür. Ahmet Bey rüyasında Murat Paşa’ya kendi minaresini yaptırdığı camide kullanmasını ister. Daha sonra bu olayı unutan Murat Paşa’nın karşısına bir gün bir kişi çıkar ve Murat Paşa’ya eski yapının minaresini kullanması gerektiğini ve bu konuda söz verdiğini hatırlatır. Murat Paşa bu durumdan nasıl bir kar elde edeceğini sorduğu zaman, kişi kendisinin Hızır Aleyhisselam olduğunu ve her gün bir vakit namazını bu camide kılacağını söyler. Bu nedenden dolayı yerel halk Hızır Aleyhisselam’ın bir vakit namazını bu camide kılacağına inanmaktadır. Bu bağlamda cami yerel halk tarafından rağbet görmektedir ve özenli bir şekilde temizlenmekte hatta bazı günler gül suyu ile yıkanmaktadır.