Bulunan kitabeye göre 1153 yılında Sultan Melik İzzetin'in emri ile Veziri Firuz Akay tarafından yaptırılan Kars Kalesi; Merkez Kale, İç Kale veya Stadel olarak anılır. Günümüze kadar gelemeyen kalenin kenti çevreleyen ve koruyan ilk yapılan dış kale surları 12. yüzyılda inşa edilmeye başlanmıştır.
Ancak 1386 yılında kente saldıran Timur tarafından kale yerle bir edilmiştir. Kaynaklara göre Merkez Kale dışında surlar 27. 000 metre uzunluğunda olup, 220 burçtan meydana gelmiştir. 1877-1878 Osmanlı-Rus savaşından sonra da kentin 40 yıllık Rus işgalinde kalması ile kale bir hayli tahrip edilmiş, orijinal özelliğini ve kullanımını yitirmiştir.
Kentten bakıldığında halen daha etkileyici bir görünüme sahip olan Kars Kalesi, 1579 yılında ise Osmanlı sultanı III. Murat'ın fermanı ile Kars'a gelen Lala Mustafa Paşa kale ve dış cephe surlarını yeniden yaptırmıştır. Kale kalıntılarında dört köşe mermer kitabe bulunmuş ve dış surların kapısına koydurulmuştur.
Kalenin tarihine ışık tutan kitabede "1152 yılında Sultan Melik İzzetin'in emri ile Veziri Firuz Akay tarafından yaptırılmıştır. Kaleyi 1386 yılında da Timur yerle bir etmiş, 1579 yılında tekrar III. Murat'ın emriyle Lala Mustafa Paşa yeniden yaptırmıştır. " Kars Kalesi içinde 12.
yüzyıldan kalma; Celal Baba Türbesi, askeri koğuşlar, tarlalar, cephanelik ve bir adet Mescit yer almaktadır. Sit alanı olarak ilan edilen Kars Kalesi'nin dış cephe surları kesme bazalt taştan yapılmış olup yük istinat duvarları ile çevrilidir.
Kalenin Sukapısı veya Çeribaşı kapısı (batıda), Kağızman kapısı (Ortakapı), Behram Kapısı veya Bayrampaşa kapısı olmak üzere üç büyük kapısı bulunmaktadır.