Selçukluların bölgede ilk olarak belirmeleri XI. Yüzyılın başlarına rastlar.

Bizans yönetiminin yöre halkına iyi davranmaması nedeniyle bozulan idari ve siyasi ortam, Selçukluları küçük topluluklar halinde bölgenin muhtelif kesimlerine yerleşmelerine imkân sağlamıştır.

Selçuklular tarafından Erzurum ve çevresine yöneltilen ilk askeri hareket 1048 yılında gerçekleştirilmiştir. Büyük Selçuklu Sultanı tarafından Erzurum ve çevresini fethetmekle görevlendirilen Azerbaycan valisi İbrahim Yanal ve Gence valisi Kutalmış Beyler, Eleşkirt üzerinden Pasinler ovasına inmiş ve oradan Erzurum üzerine yürüyerek, Erzurum kalesini kuşatmışlardır. Ancak, kuşatmanın uzun süreceğini gördüklerinden Erzurum Ovası'nın batı bölümünde yer alan zengin Erzen şehrine yönelmişlerdir. 6 gün süren bir kuşatmadan sonra Erzen Selçuklu ordusu tarafından ele geçirilmiştir.

Erzen halkı, Teodosiopolis olarak isimlendirilen bugünkü Erzurum şehri kalesine sığınmak zorunda kalmıştır. Erzen şehri bu kuşatmadan sonra yıkılıp yakılmış ve bir kez daha imar edilmeyerek metruk bir şehir halini almıştır. Bu yıkımdan sonra şehre Kara Erzen denilmeye başlanmıştır. Bu sözcük, halk dilinde zamanla Karaz şeklinde telaffuz edile gelmiştir.

Selçukluların Erzurum üzerine düzenledikleri ikinci büyük sefer, 1054 yılında Büyük Selçuklu Hükümdarı Tuğrul Bey tarafından gerçekleştirilmiştir. Ordusuyla Pasinler Ovasına geçen Tuğrul Bey, Erzurum'a gelmiş ancak Erzurum kalesinin surlarını aşamayacağını anlayarak kuşatmadan vazgeçmiştir. Bu tarihten, Anadolu'nun kapılarını Türklere açan ve Doğu Anadolu'da kesin Türk hâkimiyetini getiren günlerin müjdecisi olan Malazgirt zaferine kadar, Selçuklular tarafından Erzurum üzerine askeri bir sefer düzenlenmemiştir.

1071 Malazgirt zaferinden sonra, Erzurum ve çevresi büyük Selçuklu Sultanı Alparslan tarafından Eblul Kasım'a verilmiştir. Eb'ul Kasım, Melik Danişment Ahmet Gazi ve Emir Mengücek gibi, Doğu Anadolu'nun fethi için Büyük Selçuklu Sultanı tarafından görevlendirilen ve yaralı hizmetleri olan bir Selçuklu komutanı idi.

Erzurum'da kurulacak ve sonradan Eb- ul Kasım'ın torunlarından birisi olan Saltuk Bey'in adı ile anılacak olan beyliğin kurucusu olan Eb'ul Kasım, yörenin Selçuklu egemenliğine girmesi yönünde büyük çabalarda bulunmuştur. Merkezi Erzurum olan Saltukoğulları Beyliğinin sınırları içine zamanla Bayburt, İspir, Koçmaz, Micingirt, Oltu ve Tercan gibi önemli kale ve yerleşim yerleri dahil edilmiştir.

Eb'ul Kasım'ın 1102'de ölümünden sonra, beyliğin başına Ali ve İnanç Beygu isimli iki oğlundan Emir Ali geçti, Emir Ali'nin Selçuklu Sultanı Melik şah'ın ölümünden sonra oğulları arasında çıkan taht kavgasında Sultan Tapar'ın yanında yer aldığı ve Sultan Tapar'ın Selçuklu Devletini ele geçirmek için Silvan üzerine yaptığı seferde Emir Ali'nin de bulunduğu bilinmektedir.

Bu arada Türkler arasındaki iç mücadelelerden yararlanmak isteyen Gürcü Kralı David, 1116'da Erzurum önlerine kadar gelmiş, ancak şehir önlerinde yapılan iki çarpışmadan sonra, şehri muhasara etmekten vazgeçerek geri dönmüştür.

Gürcülerin Doğu Anadolu'daki Türk yerleşim bölgelerini tehdit altında bulundurmaları, Merkezi Konya'da kurulmuş olan Anadolu Selçuklu Devletini rahatsız ediyordu. Bunun üzerine harekete geçen Anadolu Selçuklu Sultanı Rükneddin Süleyman Şah, 1201 yılında Doğu Anadolu'daki küçük Türk Beyliklerine son verdi. Aynı tarihte Erzurum ve çevresi de Anadolu Selçuklu hâkimiyeti altına girdi. Rükneddin Süleyman Şah, Erzurum ve çevresini Mugisiddin Tuğrul Şah isimli kardeşine vermiştir. Böylece yaklaşık 130 yıl süren Saltukoğulları dönemi sona ermiş oluyordu. Anadolu Selçukluları döneminde Erzurum ve çevresi üzerindeki Gürcü baskısı büyük ölçüde kalkmış ve şehir, Anadolu'nun en gelişmiş şehirlerinden birisi olmuştur.

Mugisiddin Tuğrul Şah'ın 1225'de ölümü üzerine yerine oğlu Rükneddin Cihan Şah geçmiştir

Erzurum'daki Selçuklu Beyliğinin, kuzeyde Gürcülerle ve Trabzon'da yeni kurulmuş olan Rum İmparatorluğu ile komşu olması, bu Beyliğin Anadolu Selçukluları açısından önemini artırmaktaydı. O dönemde Anadolu Selçuklu Sultanı olan Alâeddin Keykubat, devletin güvenliğini pekiştirmek için beyliklere son veriyor ve Anadolu'daki Selçuklu hâkimiyetini güçlendiriyordu. Bu amaçla, 1228'de Erzurum'u almak üzere harekete geçti. Bunun üzerine telaşa kapılan Rükneddin Cihanşah, o sırada Ahlat'ı kuşatmış olan Celaleddin Harzemşah'tan destek sağladı.

Alâeddin Keykubad'ın Harzemlilerle barış yapma çabaları sonuç vermeyince, iki devletin ordusu, 1230'da Yassı çemen'de karşı karşıya geldi. Bu savaşta Erzurum'un Selçuklu Beyi, aynı zamanda amcası olan Alaattin Keykubat'a karşı, Celaleddin Harzemşah'ın yanında yer aldı. Savaşta Selçuklu ordusu galip geldi ve Cihanşah tutsak edildi. Bu savaş aynı zamanda Harzemliler Devletinin de sonu oldu. Savaştan sonra, Selçuklu ordusu Erzurum'a yürüdü ve çarpışma olmaksızın şehir ele geçirildi. Bundan sonra Erzurum şehri, Anadolu Selçuklu Devleti için önemli bir askeri üs vazifesi gördü.