Geleneksel Osmanlı camilerinin aksine ana yapıya bitişik olmayan minare, Murat Paşa Camii için yapılmadı. Bölgede daha önce bulunan Ahmediye Camii ile Ahmediye Medresesi'ne ait olan tarihi minare korununca, yeni inşa edilen Murat Paşa Camii'ne ikinci bir minare inşa edilmedi.

Osmanlı döneminde Beylerbeyi Murat Paşa tarafından yaptırılan cami, 12 Aralık 1572 tarihinde ibadete açıldı. Yaklaşık 520 metrekare kapalı alana ve 300 kişilik kapasiteye sahip caminin bahçesinde yer alan minare ise yapının en dikkat çeken mimari unsuru olarak öne çıkıyor.

Sekizgen kaide üzerine inşa edilen, düzgün kesme taştan yapılan silindirik gövdeli ve tek şerefeli minare yaklaşık 25 metre yüksekliğinde bulunuyor. Dışarıdan giriş kapısı bulunan minarenin içerisine girilerek merdivenlerle şerefeye çıkılabiliyor. Günümüzde görülen minare, 1920'li yıllarda yıkılan eski minarenin temelleri üzerine 1956-1957 yıllarında aslına uygun şekilde yeniden inşa edildi.

Murat Paşa Camii'nin minaresiyle ilgili halk arasında günümüze kadar ulaşan bir rivayet de bulunuyor. Anlatılanlara göre Murat Paşa, yeni camiyi yaptırırken daha önce bölgede bulunan Ahmediye Camii'nin minaresini yıkmayacağına dair rüyasında söz veriyor. Daha sonra 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 üzerine eski minare korunurken, yeni camiye ikinci bir minare inşa edilmiyor. Rivayete göre Hızır Aleyhisselam'ın her gün beş vakit namazdan birini Murat Paşa Camii'nde kıldığına inanılıyor.

Yaklaşık 12 yıldır Murat Paşa Camii'nde müezzin olarak görev yapan Fatih Şekerci, "Camimiz, Murat Paşa Camii 1572 yılında Beylerbeyi Murat Paşa tarafından yaptırılmıştır. Tabii genelde Erzurum'da tek olması hasebiyle camimizin minaresi ayrı. Genelde cemaatimizden de soran oluyorlar 'Neden ayrı yapılmış?' diye. Aslında minaremiz ayrı yapılmamış. Hemen 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 sonra minare var olduğu için tekrar Murat Paşa'ya artı bir minare yapılmıyor. O minare de Ahmediye Medresesi ve Ahmediye Camii'ne ait minare. 1930'larda falan bir depremde yıkılıyor. Daha sonra bu minare o minarenin temelleri üzerine yapılıyor. Minarenin kapısı gördüğünüz gibi dışarıda, içinden normal 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 genelde bilmiyor, tanımıyor. Onu da burada dile getirmiş olalım. Dışarıdan zaten bahçeye girildiğinde hemen dikkat çeken minarenin ayrı olması. İşte 'Minare neden ayrı yapıldı?' diye... Tabii biz de zaman zaman anlatıyoruz; var olan minareye cami aslında sonradan eklendiği için, sonradan yapılan cami minare var olduğu için tekrar minare Murat Paşa Camii'ne yapılmıyor, öyle diyeyim. Yani minare daha eski camiden" diye konuştu.