Hun ve İskitlerden sonra Anadolu’ya üçüncü Türk girişini, VIII. Yüzyıldan itibaren Müslüman Türkler gerçekleştirdiler. Abbasi Halifesi Mehdi (755 – 785) Fergana, Belh, Semerkand çevresinden getirdiği, Erzurum ve çevresine yerleştirdiği ahaliden çoğu Türk idi. Abbasi Halifesi Mütevekkil (847-861) devrinde ordunun çoğunluğunu Türklerin oluşturması, Türk nüfusunu daha da artırdı. Çağrı Bey’in 1016’da Doğu Anadolu’ya yaptığı keşif seferinde Selçuklulardan öncede bu bölgeye gelen ve akınlarda bulunan Türklerin olduğu bilinmektedir.
Selçukluların düzenli gâzası Sultan Tuğrul zamanında (l038- 1063) başladı. Musa İnanç Yabgu’nun oğlu Hasan, emrindeki ordu ile Basean/Pasin ovasını ve Erzurum ovasını istila edip Vaspuran (Van) bölgesine girdi. Hasan, daha sonra Van istikametine hareket etmiştir. Fakat Bizanslılar tarafından takip edilmiş, Vaspurakan (Van) valisi Aaron ve Gürcistandaki Kekaumenos’un da yardımı ile Stranga denilen Zap Suyu vadisinde, Hasan bey ve maiyetini pusuya düşürerek, şehit etmişlerdir. Sultan Tuğrul bu hadiseye çok üzüldü. Hasan ve ordusunun intikamının alınması için Kutalmış ve İbrahim Yinal’ı Bizansa karşı sefer için görevlendirdi.
İbrahim Yınal Türkistan’dan Nişapur’a gelen ve yurt arayan kalabalık Türkmen grubunu 1047’de, Anadolu’ya gönderdikten sonra, arkasından büyük bir ordu ile harekete geçti. Selçuklular, 1048 de Theodosiopolis’e (Karin) ve Basean (Pasin) ovasına, batıda Xaphteac (Kağdariç), kuzeyde Sper (İspir), Tayk/Taik ve Arsharunik (Oltu –Olur-Tortum-Çoruh vadisi), güneyde Haşhtenic (Hınıs ve çevresi), Toron/Taronay (Muş) yöresine Türkmen gruplarını yerleştirdi ve Khaldia, Manali ve Sembatberd gibi yöreleri aldılar. Karasu’nun kuzeyindeki Artze/Karaz’ı muhasara altına aldılar. Sursuz şehrin varoşlarında kanlı çarpışmalar oldu. Muhasaranın sonlarına doğru şehirde büyük bir yangın çıktı. Theodisiopolis’deki Bizanslı komutan Artze/Karaz’deki durumu gördüğü halde, onların yardımına koşmadı. Selçuklu akıncıları şehri ele geçirdiler. Şehir halkı Karasuyu geçerek, Theodisiopolis Kalesine sığındılar.
İbrahim Yinal, Artze/Karaz zaferinden sonra, Basean/Pasin ovasında, Artcovit bölgesindeki Kaputru (Hasenkale) önünde bulunan Kastro-Komi (Ügümü) köyünde bulunan, Kekaumenos (Ermeni), Aaron(Rum) ve Liparit(Gürcü) komutasındaki Gürcü, Ermeni ve Rumlardan oluşan Bizans ordusuna yaklaşıyordu. Bizans ordusu, Selçuklulara barış teklif etti. Ancak Kutalmış ve İbrahim Yinal bu teklifi geri çevirdi. 18 Eylül 1048 günü, Selçuklu ve Bizans kuvvetleri Kaputru’da karşı karşıya geldiler. Bir gün, bir gece süren savaşta, galibiyeti Selçuklular elde etti. Bizans generalleri ve Liparit bozguna uğradılar. Gürcistan Kralı Liparit’le birlikte çok sayıda esir alındı ve zafer nişanı olmak üzere Rey’e Sultan Tuğrul’a gönderildi.
İbn’ül Esîr, Ebu’l-Ferec, Aristakes gibi tarihçiler 1054 yılında Sultan Tuğrul’un Theodosiopolis ve ovaya hâkim bir tepeye çıkmış, durumu gözden geçirdiğini, şehrin alınmasının uzun zamana, büyük fedakârlığa mal olacağını düşünerek, buradan ayrıldığını yazmaktadırlar.
Selçuklu Sultanı Tuğrul Bey 4 Eylül 1063 tarihinde ölümü üzerine yerine yeğeni Alp Arslan Selçuklu tahtına geçti. Sultan Alp Arslan, 5 Mart1064’de Gürcistan seferine çıktı. 16 Ağustos 1064 de Ermeni merkezi Anı’yı fethetti. Kars’daki Bagratlı prensliğine de son verdi ve bu yörelere hâkim oldu. Bizans ise Theodosiopolis (Erzurum) ve çevresine sahip olmaya devam ediyordu.
Bizans İmparatoru X.Konstantinos Dukas Mayıs 1067 de öldü. Bizans İmparatoriçesi Eudokia ile evlenen Romanos Diogenes Ocak 1068 de tahtı ele geçirerek, İmparatorluğunu ilan etti. 1070 yılına kadar Theodosiopolis (Erzurum), ciddi bir tehlike ile karşılaşmamıştır.
Alp Arslan 1070’de tekrar Anadoluya girmiş ve Erçiş ile Malazgird kalelerini zaptetmiştir.
Bizans İmparatoru Romanos Diogenes, Selçuklu ordusuyla savaşmak üzere 13 Mart 1071 tarihinde İstanbul’dan yola çıktı. Sebastia (Sivas) yoluyla Theodosiopolis’e geldi. Mahiyetinde kalabalık bir ordu vardı. Themalardan (çevre kalelerden) katılan askerlerden başka, Ruslar, Abhazlar, Gürcüler, Franklar, Ermeniler, Hazarlar, Guzlar, Peçenekler ve Kıpçaklar’la birlikte 200.000 ile 400.000 arasında değişen bir güce sahip olduğu bildirilmektedir.
Romanos Diogenes, 26 Ağustos 1071 de, Alp Arslan ile Malazgirt meydan muharebesini yaptı. Romanos Diogenes esir düştü. Alp Arslan’ın isteği ile barış yapıldı ve yaralı Bizans İmparatoru Theodosiopolis’e gönderildi. Yaraları bakıldıktan sonra İstanbul’a hareket etti. Romanos Diogenes, Theodosiopolislilerin uğurladıkları son Bizans İmparatoru olmuştur. O’nun tahttan indirilmesiyle yerine VII. Mikhael Dukas İmparator oldu ve Bizans Anadolu’yu ve dolayısıyle Theodosiopolis’i Türklere terk etti.