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