Eski çağlarda halcilerin yaşadığı sahada yer alan Bayburt'un bir müddet Roma İmparatorluğu hakimiyetine girdiği ve bu imparatorluğun ikiye ayrılması üzerine Doğu Roma toprakları içinde kaldığı bilinmektedir. Bizans İmparatorluğu teşkilatına göre ülke, bugünkü eyaletlere benzer bir takım temalara ayrılmıştı. Bayburt Heldia temasına bağlıydı ve bu eyaleti meydana getiren yedi piskoposluğun dördüncüsünü meydana getiriyordu. İmparator Justinianus tarafından kalesinin tahkim ve tamir edildiği bilinen Bayburt, Arap fetihleri sırasında Bagrat sülalesinin hakimiyeti altında bulunmaktaydı.
Bayburt ve yöresi, Türklerini Anadolu'da ilk yerleştikleri bölgelerdendir. Tuğrul Bey'in Anadolu seferi (1054) sırasında Bayburt, Çoruh nehri ve Karadeniz dağlarına (Parhar) uzanan sahalara akınlarda bulunan Selçuklu kuvvetlerinin hücumlarına maruz kaldı ise de fethedilemedi. Kesin Türk hakimiyeti Malazgirt zaferinden sonra gerçekleşti. Şehir 1072'den 1202'ye kadar bazen Erzurum yöresinde hüküm süren Saltuklar'ın bazen de Danişmendiler'in hakimiyetinde kaldı. Bir ara Trabzon imparatoru I.Alexis Comnen'in kumandanı Theodore Gabras tarafından işgal edildiyse de, kısa süre sonra yeniden Danişmendli hakimiyetine girdi. (1098) Selçuklular 1202'de Saltuklu Devletine son verince Bayburt'u da ele geçirdiler.
Bayburt'un asıl gelişmesi, Süleyman Şah'ın kardeşi Erzurum Meliki Mugisuddin Tuğrul Şah ve oğlu Cihan Şah (1020-1230) döneminde oldu. Tuğrul Şah Bayburt kalesini yeniden inşa ve tahkim ettirdi. I:Alaeddin Keykubad tarafından Moğollara karşı sınırlar kuvvetlendirilirken Bayburt da Erzurum ile birlikte Konya'ya bağlandı. 1243 Kösedağ savaşının ardından Moğolların Anadolu'yu istilası esnasında yapılan anlaşma gereği Baybırt Selçukluların kontrolünde kaldı. Bu durum 1291'de burada Giyaseddin Mesud tarafından para bastırılmasından anlaşılmaktadır.
İlhanlılar devrinde Tebriz-Trabzon yolu üzerinde bulunması sebebiyle daha da gelişen Bayburt, Ceneviz ve Venedik kervanlarının konakladığı bir yerdi. Moğolistan'a giderken buraya uğrayan Marko Polo şehirde zengin Gümüş madenlerinin bulunduğunu belirtir. Hatta İlhanlılar buradan yüklü bir vergi geliri temin ediyorlardı. Bu dönemde Darül Celal adı ile anılan ve iktisadi bakımdan canlılık kazanan şehir aynı zamanda bir kültür merkezi durumundaydı. Burada Mahmudiye ve Yakutiye medreseleri kurulmuş, Mevlevilik gelişme göstermiş, ayrıca ahilik teşkilatı da yayılmıştı.
Son İlhanlı hükümdarı Ebu Said Bahadır Han'ın ölümünden sonra (1334) Bayburt, Eretnaoğulları'nın eline geçti. Zaman zaman Erzincan Beylerinin hücumlarına uğrayan şehir, bir ara Mutahharten'in idaresine girdi. Fakat çok geçmeden Kadı Burhaneddin zamanında Akkoyunlu beylerinden Kutlu Bey oğlu Ahmet Bey'in yardımı ile alındı ve Ahmet Bey'e ikta olarak verildi. Bir ara Karakoyunluların da eline geçen şehir sonra tekrar Akkoyunluların eline geçti ve uzun süre öyle kaldı.
Bayburt yöresi 1501'de bir ara Safeviler tarafından alındı. Bu dönemde Trabzon valisi olan Yavuz tarafından bun bölgeye akınlar yapıldı (1507). Yavuz tahta çıktıktan sonra da çıktığı İran seferinde bir kısım kuvvetlerini Bayburt üzerine gönderdi. Ekim 1514'te Bayburt Şah İsmail'in elinden alındı. Bundan sonra Bayburt Erzincan ile birlikte Trabzon Beyi Bıyıklı Mehmet Paşa'ya verildi ve Sancak merkezi ilan edildi.
Kanuni'nin İran seferi sırasında önemi daha da artan Bayburt kalesi 1541'de esaslı bir tamir gördü. 1553'te Şah Tahmasb'ın akınlarına şahit olunduysa da, bundan sonra XIX. Yüzyıla kadar önemli bir olay yaşanmadı. 1828-1829 Osmanlı-Rus savaşı esnasında Rus birliklerinin işgaline uğradı. 1878 ve 1916'da Ruslar tarafından yeniden işgal edilen Bayburt bu işgaller sırasında önemli oranda tahrip edildi.
1927'ye kadar Erzurum'a bağlı olan Bayburt bu tarihte Gümüşhane'ye bağlandı. 21.06.1989 tarihinde 3578 sayılı yasa ile il statüsüne kavuştu.
