Osmanlı döneminde Beylerbeyi Murat Paşa tarafınca yaptırılan cami, 12 Aralık 1572 tarihinde ibadete açıldı. Ortalama 520 metrekare kapalı alana ve 300 kişilik kapasiteye haiz caminin bahçesinde yer edinen minare ise yapının en dikkat çeken mimari unsuru olarak öne çıkıyor.
Sekizgen kural üstüne inşa edilen, muntazam kesme taştan meydana getirilen silindirik gövdeli ve tek şerefeli minare ortalama 25 metre yüksekliğinde bulunuyor. Dışarıdan giriş kapısı bulunan minarenin içine girilerek merdivenlerle şerefeye çıkılabiliyor. Günümüzde görülen minare, 1920’li yıllarda yıkılan eski minarenin temelleri üstüne 1956-1957 yıllarında aslına uygun şekilde tekrardan inşa edildi.
Murat Paşa Camii’nin minaresiyle ilgili halk içinde günümüze kadar ulaşan bir rivayet de bulunuyor. Anlatılanlara gore Murat Paşa, yeni camiyi yaptırırken daha ilkin bölgede bulunan Ahmediye Camii’nin minaresini yıkmayacağına dair rüyasında söz veriyor. Sonrasında bu sözünü unutan Murat Paşa’nın karşısına çıkan Hızır Aleyhisselam’ın verdiği sözü hatırlattığına inanılıyor. Bunun üstüne eski minare korunurken, yeni camiye ikinci bir minare inşa edilmiyor. Rivayete gore Hızır Aleyhisselam’ın her gün beş zaman namazdan birini Murat Paşa Camii’nde kıldığına inanılıyor.
Ortalama 12 senedir Murat Paşa Camii’nde müezzin olarak vazife meydana getiren Fatih Şekerci, “Camimiz, Murat Paşa Camii 1572 senesinde Beylerbeyi Murat Paşa tarafınca yaptırılmıştır. Doğal genel anlamda Erzurum’da tek olması hasebiyle camimizin minaresi ayrı. Genel anlamda cemaatimizden de soran oluyorlar ‘Niçin ayrı yapılmış?’ diye. Aslına bakarsak minaremiz ayrı yapılmamış. Derhal sizin de arkanızda bulunan Ahmediye Medresesi ve tahmini Ahmediye Camii olarak yanında başka bir cami varmış. II. Selim döneminde o cami yıkılıp yerine Murat Paşa Camii yapılıyor. Murat Paşa Camii yapıldıktan sonrasında minare var olduğundan yeniden Murat Paşa’ya artı bir minare yapılmıyor. O minare de Ahmediye Medresesi ve Ahmediye Camii’ne ilişkin minare. 1930’larda falan bir depremde yıkılıyor. Sonrasında bu minare o minarenin temelleri üstüne yapılıyor. Minarenin kapısı gördüğünüz benzer biçimde dışarıda, içinden düzgüsel merdivenlerine çıkılabiliyor. Camimizin yan tarafında bulunan Ane Hatun Türbesi var. Ağaçlıklardan ve yüksek olması sebebiyle halkımız genel anlamda bilmiyor, tanımıyor. Onu da burada dile getirmiş olalım. Dışarıdan aslına bakarsanız bahçeye girildiğinde derhal dikkat çeken minarenin ayrı olması. İşte ‘Minare niçin ayrı yapılmış oldu?’ diye… Doğal ikimiz de bazen anlatıyoruz; mevcud minareye cami aslen sonradan eklendiği için, sonradan meydana getirilen cami minare var olduğundan yeniden minare Murat Paşa Camii’ne yapılmıyor, öyleki diyeyim. Şu demek oluyor ki minare daha eski camiden” diye konuştu.
