M.S.395 yılında, Anadolu’ya ilk Türk girişi ( İskitlerden sonra) Hun Türkleri tarafından gerçekleştirilmiştir. Batı Hunlarının doğu bölümü tarafından gerçekleştirilen akınların başbuğları Kursik ve Basik komutasındaki Hun atlı birlikleri, Erzurum üzerinden hareketle Karasu ve Fırat havzalarından Malatya’ya ulaşmışlardır. 395-398 yılları arasında cereyan eden Hunların bu akınları, Çukurova ve Mezopotamya’ya kadar uzanmış, Orta ve Doğu Anadolu üzerinden Kafkas dağlarını aşarak Karadeniz kuzeyindeki yurtlarında son bulmuştur.
395 yılında Büyük Roma İmparatorluğu’nun ikiye ayrılması ile merkezi İstanbul olan Bizans (Doğu Roma imparatorluğu 395-1453) devrinde Sasanilerin Doğu Anadolu saldırıları artarak devam etmiştir. Bu saldırılara karşı müstahkem kalelere ihtiyaç duyan Bizansın Doğu Anadolu’daki generali Anatolius , 415-422 yılları arasında mevcut Erzurum Kalesini ve şehrin etrafındaki surları inşa ettirmiş ve bu şehre Bizans imparatoru II: Theodosius dan dolayı Theodosiopolis adını vermiştir.
Bizansın Doğu Anadolu’da en büyük askeri merkezi olan Theodosiopolis’i (Erzurum) 502 yılında İran Sasani Hükümdari Firuz’un oğlu Kavaz istila etmiş, şehir ve kale tahrip edilmiştir. 503 yılında D.Roma imparatoru Anastasius, Bu bölgeleri Sasanilerden geri alarak Şehri ve kalesini tamir ettirmiş, müstahkem bir mevki haline getirmiştir. Bundan dolayı şehrin adına imparatora izafeten Anastasiopolis denilmiştir. Ancak ahali bu ismi benimsememiş ve Theodosiopolis’i kullanmayı tercih etmiştir.
651 yılına kadar Bizans ve Sasani mücadelesi bölgede hız kesmeden devam etmiş, bu topraklar zaman zaman el değiştirmiştir. Ancak 531 yılından itibaren Theodosiopolis (Erzurum) Bizanslıların elinden çıkmamıştır. Şehrin en parlak devri İmparator Justinianos zamanıdır. Şehirde su kemerleri yapılması, kalenin yeniden tamiri, büyük kilise yapılması ve şehrin yeniden imar edilmesi bu dönemde olmuştur.