Kars’ın Merkez ilçesine bağlı Kaleiçi Mahallesi’nin sınırları içinde yer alan Kars Kalesi, bazı kaynaklarda Stadel ya da İç Kale ismiyle de geçebiliyor. 1153 tarihinde Selçuklu Devleti’ne bağlı Saltuklu Sultanı Melik İzzeddi ve onun veziri Firuz Akay tarafından inşa ettirilen bu tarihi yapı, asırlar boyu Kars’ın en önemli yapısı olma unvanını taşımış. Kalenin şehri çevreleyen dış surları da 12. yüzyıl içinde inşa edilmiş. Günümüzde hâlen kentin turistik açıdan en çok ilgi gören noktalarından birini oluşturan Kars Kalesi, 1386 yılında Timur tarafından yıkılmış. Kalenin yeniden inşa edilebilmesi ise ancak 1579 yılında ve Osmanlı Sultanı III. Murat’ın fermanıyla kente gelen Lala Mustafa Paşa tarafından verilen emirle gerçekleşmiş.
Lala Mustafa Paşa’nın başlattığı inşa sürecinde hem kale hem de dış surlar tekrar yaptırılmış. Bu esnada yıkılan kalenin kalıntılarının içinde bulunan dört köşeli mermer kitabe de dış kale surlarının kapısına yerleştirilmiş. 1616 ve 1636 yıllarında iki defa daha onarım çalışmasından geçirilen Kars Kalesi, 1877-1878 Osmanlı-Rus Savaşı’nda ve devamında onlarca yıl süren Rus işgalinde de ciddi tahribatlara uğramış. Tüm bu sebeplerden ötürü zamanla kullanım işlevini ve orijinal özelliklerini kaybetmiş. Ancak başına gelen tüm olaylara rağmen ve asırlar içinde gerçekleştirilen onarım çalışmaları sayesinde hâlen ayakta durabiliyor.
Kars Kalesi’nin üç büyük kapısı mevcut. Bunlar Sukapısı (Çeribaşı), Kağızman (Ortakapı) ve Behram (Bayrampaşa) olarak adlandırılıyor. Kuzeyde bulunan büyük kapı, doğrudan kalenin önündeki boş alana açılıyor. Kalenin zirve noktasını oluşturan burcuna ise taş döşenmiş bir caddeyi ve onun devamındaki merdivenleri takip ederek ulaşılabiliyor. Kars Kalesi’nin içinde 12. yüzyıla tarihlenen bir türbe, cephanelik, mescit ve askeri koğuş bölümleri bulunuyor.