Malazgird döyüşündən sonra Anadoludakı ilk Türk bəyliyi Ərzurumda qurulan Saltuklu Bəyliyi olmuşdur. Bu bəylik Ərzurumu da özünə paytaxt elan etmişdir. Saltuklu bəyliyinin qurucusu Malazgirdin qələbəsində mühüm rol oynamış Əmir Saltukdur. Malazgird qələbəsindən sonra Bizans imperatoru IV Romanos Diogenin ölümü və müqavilə şərtlərinin yerinə yetirilməməsi ilə Sultan Alparslan sərkərdələrinə Anadoluda fəthləri davam etdirmələrini əmr etdi. Bunun əsasında Əmir Saltuk Ərzurum və ətrafını fəth edərək Saltukilər bəyliyini qurdu. Böyük Səlcuqlu dövlətindən yaranan Saltuklu Bəyliyi ilə Səlcuqlu memarlığı da Ərzuruma daxil oldu. Ərzurum vilayətində öz dövrünün nəhəng tikililəri indi tarixi abidələrdir. Atabəy məscidi olaraq da adlandırılan Ərzurum Ulu məscidi 1179-cu ildə Saltukoğulları Məlik Nəsirəddin Məhəmməd bəyin (1174–1185) dövründə inşa edilmişdir. Məlik Nəsirəddin Məhəmməd bəyin dövründə tikilən Ərzurum Ulu Məscidinin "Atabəy məscidi" adlandırılmasının səbəbi Sultan Atabəy Qızıl Arslana olan sədaqət və hörmətdən irəli gəlir.

Məlum olduğu kimi, Anadoludakı Ulu Məscidlər sütunlar üzərində düz damlarla tikilmiş və örtülü həyətləri olan məscidləri nümunə götürərək tikilmişdir. Məscid Səlcuqlu memarlığına uyğun tikilmişdir. (52.5m x 41m) 2152.5 m² sahədə tikilib, daxili istifadə sahəsi 2000 m²-dir. 6000 nəfər tutumuna malikdir. Bu gün 4500 nəfər rahatlıqla eyni vaxtda namaz qıla bilir. Məscidin beş qapısı var. Qapılardan ikisi şərqdə, üçü şimaldadır. Şərqdəki birinci qapının hər iki tərəfində mehrab var və onun kənarında 1860-cı ildə təmir edilmiş kitabə yerləşdirilib. Məscidin üç günbəzi var. İlk konstruksiyasında mehrab divarı ön tərəfləri uclu tağların üzərinə qoyulmuş iri asqılı günbəzlə örtülmüşdür. İnşa edildiyi gündən indiyədək öz orijinal forması ilə gəlib çatan bu günbəz "qaranquş örtüyü" adlanan taxta örtükdür. Tikinti dizayn xüsusiyyəti ilə məscidin içindəki rütubəti yığaraq çölə axıdır. Məscid çox qapalı bir məkana bənzəsə də, bu günbəz sayəsində məscidin içərisində rütubət yoxdur. Şərq, qərb və cənub istiqamətlərinə açılan qaranquşla örtülmüş üç kiçik pəncərə var. Şimal tərəfə açılan pəncərə yoxdur. Bundan əlavə, 6000 nəfərin eyni vaxtda olduğu qapalı ərazidə səsli ünsiyyətin daha sağlam olması üçün məscidin orta hissəsinə Müqərnəs günbəzi yerləşdirilib. Arifmetik üsulla hesablanan və bərk qaya üzərində bənzərsiz formalar oyumaqla düzəldilən və yalnız Ərzurum Ulu Məscidində rast gəlinən bu müqərnəs örtük formasına bənzər başqa bir quruluş yoxdur.

Ərzurum Ulu Məscidi Ərzurum şəhər mərkəzində, Cümhuriyyət küçəsində, Qoşa minarə mədrəsəsinin qərbində yerləşir. Qoşa Minarəli Mədrəsə ilə Ərzurum Ulu Məscidi arasında heç bir bina yoxdur. Onlar bir-birinə qonşudurlar. Ərzurumdakı bütün digər məscidlərdə Ramazan ayında cümə və bayram namazları, təravih namazları qılınsa da, Ərzurumluların diqqətlə ibadət etməyə üstünlük verdiyi yer məhz bu məsciddir.