Yapılış tarihi bilinmeyen Taşhan (Bedesten) Ulu Cami’nin yakınında şehir içerisindedir. Taşhan geçirdiği bir yangından sonra kitabeleri kaybolmuştur. Bedesten (Taşhan) üç bölümden meydana gelmektedir. Her bölüme ayrı kapıdan girildiği için ayrıca etrafı binalarla kaplı olduğu için üç mekân ilk bakışta birbirinden ayrı olarak görünür.
Ana mekân kare şeklindedir. Ortada çok kuvvetli bir paye bulunur. Bu payeden dört yöne atılan sivri kemerlerin meydana getirdiği dört bölümün üzeri kubbelerle örtülüdür. (R.225–226) bu kubbelerden biri ilk durumunu kaybetmiştir. Yayvan kubbelerde açılan pencerelerde orijinal değildir.
Yapının kare mekânı sıva ile kaplı olmasına rağmen dikdörtgen kısımda olduğu gibi taş ve tuğladan inşa edildiği görülmektedir. Giriş bölümünün üzerinde bir aydınlık feneri vardır. Giriş kapılarının hepsinin bir taş tezyinata sahip oldukları kalan mevcut kısımlardan anlaşılmaktadır. Asıl giriş kapısını üzerinde üç dilimli bir kemer görülmektedir. (R.227) Sathi kemerler içinde açılan kuzey ve batı kapılarında oldukça güzel ince işlenmiş taş tezyinat dikkati çeker. Sonradan örülen bu kapılar, yan mekânlara geçit verirdi.
Kare şeklindeki ana mekanın batısındaki ikinci mekan dar dikdörtgen şeklindedir. arka arkaya sıralanan kubbe ve tonozla örtülüdür. Ortadaki geniş tonozun iki yanında bulunan kubbeli kısımlara, esas mekanın batı yönüne bakan kubbeli bölümler arasında birer kapıya irtibat sağlanmıştır. Kubbelere geçiş Türk üçgenleriyle sağlanmıştır. ara bölümler sathi sivri kemerlidir. İkinci mekan daha büyük ölçüdedir. geniş bir kemerle diğer kısımlardan ayrılır. Yapı bir beşik tonozla nihayetlenir.
Bayburt Bedesteni (Taşhan), II. Beyazıt (1481–1512 ) in kapı ağası Hüseyin Ağa tarafından yaptırılan Amasya, XVII. Yüzyılda Fazıl Ahmet Paşa tarafından yaptırılan Vezir Köprü (198) ve bilhassa plan ve ölçü bakımından bunu çok andıran ve eskiden bedesten olduğu söylenen Zile Camii ile büyük bir benzerlik gösterir. Hepsinde ana mekân kuvvetli bir paye ve dört yöne açılan kemerlerle dört bölüme ayrılmıştır. Her bölüm birer kubbeyle örtülüdür.
Bayburt bedesteninin Yavuz Sultan Selim 2512–1520) zamanında hapishane olarak kullanıldığı söylenmektedir. Bu bedestenin Vezirköprü be3desteninden daha eski olduğu düşünülebilir.
Evliya Çelebi XVII. Yüzyıl başında Bayburt ‘ u ziyaret ettiğinde bu bedesten vardı. Evliya Çelebi bu bedestenden “ Gayet müzeyyen ve Zarif “ bir bedesten olduğunu anlatmaktadır. (199)