Bayburt Kalesi liegt innerhalb der Stadt auf einem steilen Felsvorsprung oberhalb des Yıldırım Çayı.
Es ist nicht genau bekannt, wer die Festung ursprünglich erbaut hat. Eisenzeitliche Scherben lassen auf einen urartäischen Vorgängerbau schließen. Der heutige Bau ist eine osmanische Festung mit seldschukischem Vorgängerbau.
Die Festung befand sich an einer wichtigen Handelsstraße über das Zigana-Gebirge und dem Kop Dağları'nın.  Diese Straße, die das Schwarze Meer mit dem Persischen Golf verband, war für Reisende und Kaufleute von großer Bedeutung. Ein bekannter Besucher der Stadt war Marco Polo. Auf seiner Reise nach China verweilte er in Bayburt. Er berichtet von den Silberminen der Umgebung.

Die Stadt Bayburt und damit auch die Festung wurde von vielen Völkern beherrscht, beispielsweise durch die Urartäer, Armenier, Perser, das Römische Reich und die Seldschuken sowie durch die Osmanen. Die Mongolen wurden hier 1364 von Alexios III., dem Kaiser von Trapezunt, besiegt. 1462 kämpfte hier der osmanische Sultan Mehmed II. gegen die Akkoyunlu, eine  turkmenische Stammesföderation. 1825 wurde Bayburt Kalesi, ebenso wie die Stadt selbst, bei einer Invasion der Russen völlig zerstört. Die Stadt wurde wieder aufgebaut.

Die meist 30 Meter hohen Mauern der Burg haben ein Länge von 2 km. Ihre größte Länge in nord-südlicher Richtung beträgt knapp 500 Meter. Nach einem Besuch in Bayburt im Jahr 1647 notierte Evliya Çelebi, ein osmanischer Schriftsteller, dass sich in der Festung eine Siedlung mit 300 Häusern und eine Moschee befinden.

Die Burg wird seit 2017 aufwändig restauriert und archäologisch umfassend untersucht.