Kars’ın Kaleiçi Mahallesi’nde dik yamaçlı bir tepe üzerinde bulunan yaklaşık 900 yüzyıllık tarihi bir yapıdır. MÖ VIII. yüzyılda bölgeye hâkim olan Urartu devleti tarafından yapıldığı bilinmektedir. Saltuklu Sultanı Melik İzzeddin’in emri ile veziri Firuz Akay tarafından 1153 yılında yeniden inşa edilmiştir. Timur’un Anadolu’yu işgali sırasında kale yıkılmıştır. Osmanlı döneminde Sultan III. Murat’ın isteği ile Lala Mustafa Paşa tarafından 1579 yılında kale ve dış cephe surları yeniden yaptırılmıştır. Osmanlı kaynaklarından elde edinilen bilgiler doğrultusunda kalenin yapımında 100 bin asker kullanıldığı belirtilmektedir. Bunu belirten bir kitabe de dış surların kapısında bulunmaktadır. Kars Kalesi, 1606 yılında İran Şahı I. Abbas tarafından yıkılmıştır. 1616-1636 yıllarında iki kez onarılmıştır. Bu onarımlar yapılırken Kars şehir merkezine de yeni yapılar inşa edilmiştir. Kale 1877-1878 Osmanlı-Rus savaşında tahribata uğramış, orijinalliğinden kısmen de olsa uzaklaşmıştır.

Kalenin çevre uzunluğu 4.200 metre olup 220 burç bulunmaktadır. Bu burçlardan sadece yedi tanesi günümüze ulaşabilmiştir. Kale iç ve dış kale olarak iki bölümden oluşmaktadır. Kenti çevreleyen dış kale surları XII. yüzyılda inşa edilmiştir. Dış surlar beş sıra halindedir ve bu surlar kesme bazalt taşından yapılmıştır. Ayrıca bu surların önüne derin hendekler kazılmıştır. Kalenin 2.080 mazgalı bulunuyor. Kalenin üç büyük kapısı olup bu kapılardan batıdaki Su Kapısı (Çeribaşı Kapısı), güneydeki Kağızman Kapısı (Orta Kapı) ve doğudaki Behram Kapısı (Bayrampaşa Kapısı) olarak adlandırılmaktadır. Bunlardan kuzeydeki ana giriş kapısı ise kale önündeki bir uçuruma doğrudur. Kale burcuna ise taş döşeli bir yol ve yolun bitiminde de merdivenlerle ulaşılmaktadır. Kars Kalesi’nin içerisinde türbe, askeri koğuşlar, cephanelik ve bir de mescit vardır. Bu türbe, Gürcü-Kıpçaklar ile Saltuklular arasında yapılan savaşlar sırasında ölen ve bu savaş sırasında Kars Kale komutanı olan Celal Baba’ya aittir. Günümüzde Kars Kalesi, Kültür ve Turizm Bakanlığı tarafından birinci derece arkeolojik sit alanı olarak korunmaktadır.