Şehir, tarih boyunca birçok farklı kavmin akınlarına uğramış, bu kavimler arasında Kimmerler, İskitler, Medler ve Persler bulunmaktadır. Xenophan, eserinde şehirden kalabalık ve zengin bir yerleşim yeri olarak bahsetmektedir.
M.Ö.2. yüzyıldan itibaren şehir, Pontus krallığına bağlı kalmış, ardından Roma hakimiyetine geçmiştir. Tarihi kalenin Urartular döneminde inşa edildiği ve Roma İmparatoru Justinianus döneminde onarıldığı bilinmektedir. Şehir, tarihi boyunca Emevilerin, Bizanslıların, Selçukluların ve Moğolların hakimiyetine girmiştir. Akkoyunlu Devleti'nin kuruluşuna da ev sahipliği yapan Bayburt, 1514'te Osmanlı İmparatorluğu'nun kontrolüne geçmiştir.
Evliya Çelebi, seyahatnamesinde bu bölgenin zenginliğinden ve öneminden bahsetmektedir. 1828'de Rus işgaline uğrayan Bayburt, bu dönemde büyük yıkımlar yaşamış, ancak daha sonra bu işgalden kurtulmuştur. Birinci Dünya Savaşı sırasında şehir, Ruslar ve Ermenilerin işgaline uğramış, bu işgaller sırasında halk büyük acılar çekmiştir. Ancak, 1918'de bu işgalden kurtulmuş ve Cumhuriyet dönemine kadar çeşitli değişiklikler yaşamıştır. Bayburt, 1989 yılında il statüsü kazanmıştır.
Bayburt'un eski adı "Gymnias" olarak bilinir. Bunun dışında tarih boyunca farklı kaynaklarda ve dönemlerde şehir için kullanılan diğer isimler şunlardır:
Payberd (Ortaçağ Ermeni kaynaklarında)
Payper, Baberd, Paypert (Bizans kaynaklarında)
Painpurth, Baiburt (Marko Polo’nun seyahatnamesinde)
Bâbirt (Arap kaynaklarında)
Pâpirt (Akkoyunlu tarihi kaynaklarında)
Bu isimler, Bayburt'un tarihi boyunca hangi medeniyetlerin hakimiyeti altında olduğuna, hangi kültürlerle etkileşimde bulunduğuna ve bölgenin coğrafi ve stratejik önemine bağlı olarak değişiklik göstermiştir.