Ali Paşa Camii, giriş kapısının üzerinde bulunan dört satırlık kitabede yazan bilgiye göre Erzurum’da bir süre valilik yapan Ali Paşa tarafından 1570 senesinde yaptırılmıştır.

Ali Paşa Camii, beş gözlü son cemaat yerine sahip, ahşap destekli ve ahşap tavanlı camiler grubunda yer almaktadır. Caminin kuzeyinde bulunan ve altı adet ahşap sütun ile taşınan son cemaat yerinin üzeri öne doğru eğimli bir çatı ile kapatılmıştır. Caminin güney ve kuzey cephelerine iki, doğu ve batı cephelerine ise iki tane olmak üzere toplamda dört tane pencere yerleştirilmiştir. Bu pencerelerin her biri dikdörtgen formdadır. Caminin giriş kapısı kuzey cephededir. Giriş kapısının kemeri iki taraftan seki şeklinde yükseltilmiştir. 

Eserin mahfil bölümü asıl ibadet mekânının kuzeyinde bulunmaktadır. Caminin minaresi ise kuzeybatı köşeye yerleştirilmiştir. Tuğla malzeme kullanılarak inşa edilen minare silindirik bir yapıya sahiptir. Minarenin kaide bölümü beden duvarları boyunca yükselmektedir. 

Caminin mihrap kısmında taş malzeme kullanılmıştır. Mihrap nişi bir çerçeve içerisinde beş kenarlı ve mukarnas kavsaralı olarak yapılmıştır. Çakma tekniği kullanılarak yapılan minber bölümüne mihrabın sağında yer verilmiştir. Ancak caminin orijinal minberi 1994-1995 yılında değiştirilmiştir. Günümüzdeki minber orijinal değildir. 

Caminin avlusunda taş sütunlu ve kemerli olarak planlanmış çeşmeler bulunmaktadır. Çeşmelerin iki köşesinde de bu çeşmeleri kimin yaptırdığı veya kimin tamir ettirdiği gibi bilgilerin bulunduğu iki farklı kitabeye yer verilmiştir. Bunlara ek olarak caminin avlusunda bir de hazire bölümü yer almaktadır. Bu hazirede Hacı Ahmet Efendi, Hafız Mehmet Sabit Efendi, Mehmet Şükrü Efendi’ye ait olduğu bilinen mezarlar bulunmaktadır.