Osmanlı kervansaray mimarisinin en başarılı örneklerinden biri olan kervansaray, plan, mimari ve malzemesi ile klasik Osmanlı Dönemi kervansaray yapılarının bölgesel bir örneğidir. Kervansarayın batı giriş kapısı üzerinde sülüs hatla yazılmış mermer kitabede Kanuni Sultan Süleyman’ın veziri Rüstem Paşa’nın (1500–1561) ismi ve bir de ribat kelimesi geçmektedir.  

Tarih kısmı kırılan kitabenin metni şu şekildedir:

… Er-ribat fi eyyami devleti el…

…El-a’zam Rüstem Paşa yesserallahu…

Kitabede geçen ribat kelimesi kervansarayların tarihsel gelişimi içerisinde Orta Asya’dan İran ve Anadolu’ya taşınan bir yapı örneği olduğunu belgeleyen ve bu yapı türünün kökeni ve gelişimi konusunda bize bilgi vermesi bakımından son derece kıymetli bir kelimedir. Osmanlı Dönemi’nin en zengin yöneticilerinden olan Rüstem Paşa, inşa ettirdiği yüzlerce eserin yanı sıra bağışladığı gelirlerle de ayrı bir yere sahiptir.  Kurduğu vakıflarla ülkenin farklı coğrafyalarında İstanbul başta olmak üzere, Anadolu’nun birçok yerinde, Rumeli’de, Macaristan’da, Hırvatistan’da Medine’de, Kudüs’de, Mısır’da ve Bakanlarda birçok hayır eseri inşa ettirmiştir. Arşiv belgelerinden öğrenildiği kadarıyla Rüstem Paşa Erzurum’da bir han, bir bedesten, bir hamam ve 65 dükkân vakfetmiştir.

36.50 x 43.50 metre ölçülerinde, iki katlı açık avlulu simetrik bir düzenlemeye sahip olan Erzurum Rüstem Paşa Kervansarayı, 20.00x20.00 metre ölçülerindeki açık avlunun etrafı dört yönden revaklarla çevrilidir. Revakların gerisinde 31 oda yer almaktadır. Batıdaki asıl girişten başka, doğu ve kuzey cepheden derin birer eyvanla avluya ulaşılan birer kapı daha açılmıştır. Bu odaların büyük bir bölümü bir kapı ve bir pencere ile revaklara açılmaktadır. Odalar, eyvanlar ve revaklar beşik tonozla örtülü iken, köşe odalarından güneybatıda olanı kubbe ile örtülüdür. Rüstem Paşa Kervansarayının avlusuna girişi sağlayan batıdaki ana kapının üstü mescid olarak düşünülmüştür. İkinci kattan merdivenlerle çıkılan dikdörtgen planlı mescidin batıya açılan iki penceresi bulunmaktadır.

Yapının ikinci katına ise dört yönde cephelerin orta kesiminde açılan girişlerle ulaşılmaktadır. Güneydeki giriş Rüstem Paşa tarafından kervansaray için vakfedilen Kırkçeşme Hamamı tarafından gelen sokağa açılır. Doğu cephedeki ikinci kat kapısı zamanla fonksiyonunu yitirmiştir. Kervansarayın doğu kesiminde bulunduğu bilinen ahır kısımlarının üstünde yer aldığını tahmin ettiğimiz merdivenlerle doğudaki kapıya ulaşılmakta idi ancak bu merdivenler günümüzde mevcut değildir.

Orijinalinde toprak damla örtülü olan yapının tonoz ve kubbeleri Cumhuriyetin ilk yıllarında kurşun levhalarla kaplanmıştır. Kervansaraya son restorasyonlarla ocak bacaları eklenmiştir. Rüstem Paşa Kervansarayı 1965 yılında önemli bir onarım geçirmiş ve yapının kuzey duvarına bitişik kısım yeniden yapılmıştır. Son onarım ise 2007 yılında Erzurum Vakıflar Bölge Müdürlüğü tarafından gerçekleştirilmiştir. Günümüzde Erzurum için yöresel bir taş işçiliği olan Oltu taşı imalat ve satış yeri olarak hizmet vermektedir.