M.Ö. ki yüzyıllardan zamanımıza kadar zengin arkeolojik malzeme bize Erzurum’un geçirdiği milletler hakkında malumat vermektedir. Karaz ve Pulur höyüklerinde yapılan kazılarda ele geçen çanak çömleklerden anlaşıldığına göre , Erzurum’un ilk bilenen halkı Urartular dır. Bunu Hititler, Ermeniler, Medler, Persler, Partlar, Romalılar, Sasaniler, Emeviler, Abbasiler, Bizanslılar ve Türkler takip etmişlerdir. Tarih kaynakları gözden geçirildiğinde Karintis, Karin/Garin, Karana, Karnoi Kalghak, Karnoi Kağak gibi ayni, ancak farklı yazılışlar Erzurum’un ilk adı olmaktadır. Ermenilerin ( Karnei Kalhak = Karin mintikasının beldesi) dedikleri yere Türklerin “KARUNİLİ” dedikleri, Kitab-ı Dede Korkut’da bu isimle Erzurum’un kastedildiği ifade edilmektedir. Bizanslılar, M.S. 415-422 yılları arasında bu bölgedeki Erzen’in (Karaz köyü civarı) güney batısında, doğudan gelen saldırılara karşı müstahkem bir şehir kurmuşlardır. Bizans ordusu komutanı Anatolius bu şehre İmparatoru II. Theodosius adına izafeten Theodosiopolis (Theodos şehri) adını vermiştir. Birçok savaşta tahrip olunan şehir (Erzurum) 504 yılında Bizans İmparatoru Anastasius tarafından yeniden tahkim ettirilmiş ve kendi ismine izafeten Anastasiupolis denilmişse de, imparatorun ölümünden sonra bu isim terk edilerek Theodosiopolis ismi kullanılmıştır. VIII. Yüz yılda Anadolu’ya İslam fetihlerinin başladığı sıralarda İslam yazarlarından El-Belâzurî, Futuhul Büldan’da “Erzurum ve çevresinde Bizans otoritesi oldukça zayıflamış, hatta buradaki topraklar birkaç beylik arasında bölünmüştü. Bu beyliklerin birisinin başında adı KALİ olan bir kadın vardı. Bu kadın bu beyliklerin tümünün üzerinde etkisi olan Ermanyakus’un kızıydı. Kali, bir şehir yaptırdı ve şehir KALİKALE adıyla anılmaya başladı.” demektedir. Emevi ve Abbasiler Rumca ismi kaldırarak, Kâlikale ismini kullandılar. Taberi, Vakidi ve diğer İslam yazarları hep bu adı zikrettiler. X. Asır İslam coğrafyacıları Kalikale şehri hakkında malumat vererek, şarkta ev eşyasının en mühimi sayılan Kali’nin (yani halının) burada yapıldığını ve adını bu şehirden aldığını söylemişlerdir.Buraya mensup olan âlimler de, Kâli ismini kullanmışlardır. Bunlar arasında Kadı Ebû’l-Asba’el Kâli, dil bilimcisi Ebû Ali el-Kâli zikredilebilir.
949 yılında Bizans İmparatoru 7. Kostantinos ‘un orduları Erzurum’a hâkim olarak İslam idaresine son vermişler ve 1071 yılına kadar şehrin adı Theodosiopolis olarak kullanılmıştır.
Theodosiopolis kalesinin kuzeybatısında, Karasunun sağ tarafında kalan Artze/ Arza (Karaz) şehri XI. yüzyıl kayıtlarına göre zengin, kalabalık nüfusa sahip, kalesi olmayan yerleşme alanı olarak belirtilmektedir. Selçuklu Sultanı Tuğrul Bey kardeşi İbrahim Beyi Kutulmuş ile beraber Rum bölgesine gönderdi. Selçuklular H.440 – M. 1048 yılında bölgenin en zengin şehrini ele geçirmiş, kıymetli madenlerden ve silahlardan oluşan çok büyük ganimetler elde etmişlerdir. Şehir Türkler tarafından tahrip edildiğinden, sağ kalan şehir halkı Theodisiopolis’e sığınmış ve eski şehirlerinin adını da bu şehre vermişlerdir. Bu durumdan sonra şehir dört adlı bir şehir olmuştur. Müslümanlar KALİKALA, Ermeniler KARİN, Rumlar THİODOSİOPOLİS, Mülteciler (Artzn/ Arzn) ERZEN diyorlardı.
İlk İslam halifeleri zamanında fethedilen yerler arasında iki ERZEN isminde şehir vardı. Birisi İran’da Şiraz yakınında idi. İkincisi Hazreti Ömer zamanında sulh yoluyla fethedilen Siirt ile Meyyafarikin (Silvan) arasındadır. ERZEN şehri Bizanslılardan alındıktan sonra diğerleriyle karıştırılmasın diye (Rum Erzeni ) mânasına ERZEN-İ RUM denilmiştir. Selçuklular tarafından Erzurum’da basılmış paraların üzerinde şehrin adı Arzan al-Rum, Erzenü’r-Rum, Erzen-i Rum ve Erz-i Rûm şeklinde yazılmıştır ve nihayet bugünkü Erzurum şeklini almıştır.