Eski bir Osmanlı sınır kenti olan Bayezid’in yedi kilometre güneydoğusunda, Belleburç adı verilen mevkiide, Karaburun tepelerinin sert kayalıkları üzerine bina edilmiştir. Kalenin oturduğu zemin, kayalık olduğu için plana fazla uyulmadan, kayaların durumuna göre inşa edilmiştir. Bu bölgede yüksek tepelere yapılan kaleler, yarı işlenmiş taşlardan yapılan duvarlardan meydana gelmektedir. Kalelerin eteğinde ise küçük yığma tepeciklerin altında tek kişilik örgü mezarlar bulunmaktadır. İshak Paşa Sarayı ise kalenin güneyinde bulunmaktadır. İki yapıyı aralarına giren vadi ayırmaktadır. Kalede bulunan kaya mezarı örneği (MÖ XIII-IX) ve kalenin temelinden çıkarılan taşların cins ve kesim şekilleri, kalenin Urartu Uygarlığı’na tarihlenmesine neden olmuştur. Kalenin isminin Urartu döneminde Daryunk olduğu tespit edildi. Cenevizlilerin bu bölgeyi ticari geçiş yolu olarak kullanmalarından ötürü, bölge halkı, bu kaleyi Ceneviz Kalesi olarak da bilmektedir. Bayezid adı, Celâyirli (Celâyiroğulları) hükümdarı Sultan Ahmed Celâyir’in kardeşinin isminden gelmektedir. Kale, isim sahibi olan Sultan Bayezid tarafından 1374 yılında onarıldı. Bayezid Kalesi üç kısımdan oluşmaktadır. Kalenin orta kısmında mağaralar ve ibadethane kalıntısı yer almaktadır. Yavuz Sultan Selim’in Çaldıran Seferi esnasında, ordu Bayezid yakınlarında konaklamıştır. Bu sırada, Bayezid Kalesi’nin halkı kendi istekleri ile Osmanlı’nın himayesine dolayısıyla kale de Osmanlı topraklarına girmiştir. Kale, Osmanlı döneminde Mahmut Paşa’nın Sancakbeyi (1722-1767) ve İbrahim Paşa’nın (1763) Erzurum Beylerbeyi olduğu zaman diliminde onarım geçirmiştir. Kalenin surlarının ve iç kalenin XIX. yüzyıla kadar sağlam olduğu bilinmektedir. Bayezid Kalesi, Rus Savaşları ve Birinci Dünya Savaşı sırasında tahrip olmuştur. Kalenin surlarının daha önceden İshak Paşa Sarayı’nı da kapsayacak şekilde bütün şehri çevrelediği dönemin gravürlerinden görülebilmektedir.