Bayburt Kalesi lies within the city on a steep rocky outcrop above the Yıldırım Çayı.
It is not exactly known who originally built the fortress. Iron Age fragments suggest that a Urartian predecessor was built. The today's building is an osmanische fortress with seldschukischem predecessor building.

The fortress was located on an important trade route over the Zigana Mountains and the Kop Dağları'nın. This road, which connected the Black Sea with the Persian Gulf, was of great importance for travellers and merchants. A well-known visitor to the city was Marco Polo. On his trip to China he stayed in Bayburt. He tells of the silver mines in the area.

The city of Bayburt and thus also the fortress was ruled by many peoples, for example by the Urartians, Armenians, Persians, the Roman Empire and the Seljukes as well as by the Ottomans. The Mongols were defeated here in 1364 by Alexios III, the emperor of Trapezunt. In 1462, the Ottoman Sultan Mehmed II fought here against Akkoyunlu, a Turkmen tribal federation. In 1825 Bayburt Kalesi, as well as the city itself, was completely destroyed by an invasion of the Russians. The city was rebuilt.

The walls of the castle are mostly 30 meters high and 2 km long. Their greatest length in a north-south direction is just under 500 metres. After a visit to Bayburt in 1647, Evliya Çelebi, an Ottoman writer, noted that the fortress contained a settlement with 300 houses and a mosque.

Since 2017, the castle has been extensively restored and archaeologically extensively investigated.