Erzurum, Fevziye Mahallesi’nde, Menderes Caddesinde, Pervizoğlu Camisi ile Boyahane Hamamı arasında bulunan Rüstem Paşa Bedesteni'ni Kanuni Sultan Süleyman’ın Sadrazamı Rüstem Paşa 1544-1561 arasında yaptırmıştır.
Erzurum’un işlek kervan yolları üzerinde bulunmasına rağmen şehirde nedense kervansaray yapılmamıştır, Osmanlı döneminde yapılan hanların başında Rüstem Paşa Hanı gelmektedir. Bu yapı kaynaklara kervansaray veya bedesten olarak geçmiş olmasına karşılık mimari yapısı ve özellikleri han olarak yapıldığını göstermektedir.
Rüstem Paşa Bedesteni'nin mimari yönden ilgin çekici bir plan düzeni ve yapısı vardır. Burada dikdörtgen bir avlu çevresinde, kesme taştan yapılmış revakların arkasına sıralanmış odalardan oluşan iki katlı bir yapıdır. Doğu ve batı yönünde sivri kemerli ve tonozlu iki kapıdan girilen avlunun çevresinde 32 hücre bulunmaktadır. Avluda kalın payelerin yuvarlak tuğla kemerlerle birbirine bağlanmasından oluşan bir revak sistemi meydana gelmiştir. Üzerleri tonoz örtülü olun bu revakların arkasındaki odalar da basık tonozlarla örtülmüştür. Üst katta yine koridor çevresinde sıralanmış basık tonozlu odalar bulunmaktadır.
Vakıflar Genel Müdürlüğü tarafından 1970 yılında restore edilen, çarşı olarak kullanılan hanın günümüzde üst katlarında Oltu taşı işlemecileri, alt katlarda ise çeşitli işyerleri bulunmaktadır.
