Erzurum'un bilinen ilk adı Doğu Roma (Bizans) İmparatoru II.Theodosios' a (408-450) izafe edilen Theodosiopolis' ti, şimdiki Erzurum' un yerinde kurulmuştu. IV. asır sonuna doğru Roma imparatorluğu sınırları içine alınmış ve 415 tarihinde Theodosios' un emriyle Şark Orduları Kumandanı Anatolius tarafından kurulmuştur. Urfalı Mateos' a göre bu şehir Garin mıntıkasında Fırat'ın kaynağına yakın bir yerde bulunuyordu. Belazurî bölgeye hakim olan Ermenyakos' un ölümü üzerine yerine geçen Kali adlı karısı tarafından kurulduğu için Araplarda Kalikala (Kali' nin ihsanı) adını vermişlerdir. Belazuri Kalîkala' yı dördüncü Ermeniyye şehirleri arasında sayar ve Ermeniyye şehirlerinden biri olarak kabul eder. X. asır İslam coğrafyacıları Kalikala şehri hakkında bize malumat vererek, doğuda ev eşyasının en önemlisi sayılan Kali (halı)nın burada yapıldığım ve adını bu şehirden almış olduğunu kaydetmektedirler. Hudud alalam' ın yazarı bu şehrin müstahkem bir kalesi bulunduğunu ve her taraftan gelen gazilerin burayı nöbet tutarak koruduklarım Ve şehirde tüccarların çok olduğunu bildirmektedir. Bugünkü Erzurum adı ise, Erzen' in Selçuklular tarafından fethedilmesi üzerine ahalisinin Theodosiopolis' e (Kalikala=Karin) göç etmelerine müteakip bu şehre Erzen ve Türk hâkimiyetinin ilk safhalarında bu adın sonuna, Meyyafarikin (Silvan) ile Siirt arasındaki Erzen' den ayırmak ve Anadolu'ya ait olduğunu belirtmek üzere Rum kelimesi ilave edilerek, Erzen al-Rum denilmesinden kaynaklanmıştır. Selçuklular tarafından Erzurum'da basılmış paraların üzerinde şehrin adı Arzan al-Rum şeklinde yazılmıştır. Daha sonra Erzurum şekline dönüşmüştür.