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.
Bölgeye hâkim 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.
Hüsala Erzurum şehri tarih boyunca aşağıdaki isimleri taşımıştır:
1-Karanilis - Karanitide - Garin - Karin - Kalak - Karun - Kalak (Yunan, Bizans, Roma kaynaklarında, Ermeni ve Gürcü tarihlerinde)
2-Theodosiopolis (Bizans Dönemi)
3-Kali-Kala (k) (Kali/Han-Şehri) (İslam kaynaklarında).
4-Arzan - Arzen - Artze (Şimdiki "Karaarz - Karaz" yerinde) (Selçuklu fethi sırasında).
5-Erzen - Rum / Erzen-ir-rüm ve Erzurum (Selçuklu, İlhanlı, Akkoyunlu, Osmanlı çağlarında)