1579 tarihinde Osmanlı Padişahı III. Murad’ın emri ile Lala Mustafa Paşa tarafından Kars şehrini yeniden imar çalışmaları sırasında yaptırıldığı düşünülen Vaizoğlu Camii, Kaleiçi Mahallesi Mimar Oktay Ekinci Caddesi’nde, İç Kale’nin güney eteklerinde bulunmaktadır.

1604 yılında, Safeviler’in işgali ile yıkılan cami, kitabesine göre 1646 yılında Vaizzadelerden Hacı İbrahim Halil tarafından yeniden yaptırılmıştır. 1915 yılında, Ruslar tarafından minaresi yıkılmış ve 1976 yılına kadar bakımsız ve harap bir durumda kalmıştır. Bu tarihte yeniden onarılarak ibadete açılmıştır. Son yıllarda yeni bir restorasyon geçirmiştir.

Bazalttan ince ve kaba yonu taş malzemeden inşa edilen cami, yaklaşık kare planlıdır. Cephelerde yer yer devşirme malzemeye de rastlanır. Kuzeydeki taçkapısı sivri kemerli dar bir eyvan içerisinde basık kemerlidir. Kapı kemerinin hemen batısında, bugün için öndeki sundurmanın ahşap ayağı altında kalmış olan kitabesi bulunur. Caminin harimi dört ahşap sütun tarafından taşınan düz ahşap bir tavan ile örtülüdür. Ortadaki sütunlar, tavan göbeğinde kare bir alanı meydana getirir. Mihrap nişi, bazalttan kesme taş malzemeli ve dikdörtgen bir çerçeve içerisinde sivri kemer formludur. Nişin içerisi beş köşeli olarak düzenlenmiştir.