Erzurum şehir merkezinde Cumhuriyet Caddesi’nde, Yakutiye Medresesinin doğusunda bulunmaktadır. Cami aslında külliye programında inşa ettirilmiştir.Lala Mustafa Paşa Camisi Kıbrıs fatihi Lala Mustafa Paşa tarafından Erzurum’da Beylerbeyi olarak görev yaptığı sırada 1562 yılında yaptırılmıştır. Cami Mimar Sinan’ın eseri olduğu söylenilse de o dönemde Sinan'ın kalfalarından birinin yaptırmış olabileceği düşünülür.
Klasik osmanlı mimarisini yansıtan merkezi plan uygulaması burada da karşımıza çıkmaktadır.Caminin beş gözlü son cemaat yerinde sağdaki mihrabiye üzerinde yer alan 14 satırlık nesih yazıyla yazılmış vakfiyesi yer alır.Kubbesi dört taşıyıcı üzerine oturmaktadır. Doğu batı ve kuzey tarafta açılan dört kapısı bulunur.Kuzey taraftaki kapı cümle kapısıdır.Mukarnas kavsaralı olan taç kapıdan harim kısmına geçilir.Mihrabı taç kapının formunda ele alınmıştır.Kuzeybatıda yer alan minaresi kesmetaş malzemeli olup tek şerefelidir.Sivri kemerli pencere alınlıklarında yazı ve nebati kompozisyonlu çini süslemelere yer verilmiştir.İç ksındaki çiniler günümüze kısmen ulaşmıştr.Ancak dış kısımdaki çiniler tahribattan ötürü günümüze ulaşamamıştır. Lala Mustafa Paşa caminin yanında saray ve bir de sıbyan mektebi yaptırmış ancak, bunlar günümüze ulaşamamıştır. Caminin yanı sıra hamamı bugün ayaktadır.
