Great Mosque of Erzurum was commissioned by Saltukid ruler Nasr al-Din Muhammad and built by Abu al-Fath Muhammad in 1179/575 AH. According to inscriptions found at the mosque, five restoration projects were undertaken in different periods; first by the governor Hüseyin Paşa in 1639, second by Mosque caretaker Ali Efendi in 1826, third by Mahmut II (1785-1839), fourth by governor Ibrahim Ethem Paşa in 1860 and the last by the General Directorate of Religious Endowments (Vakiflar Genel Müdürlügü) between 1957-1964. The repairs have resulted in the partial modification of the old dome and vaulting system. Some portions of the mosque were demolished and rebuilt over the years in a variety of architectural styles. A portion of the central aisle and large sections of the qibla wall are remaining from the original Saltukid mosque. 

The mosque has a rectangular plan about forty-one by fifty-four meters in area. The main entrance is on the north side and is covered with a muqarnas hood. The mosque has four other entrances, two on either sides of the main portal, that were re-built along with sections of the northern wall in the nineteenth century, and two others on the east façade. While the northern entrances are arranged symmetrically, the two doors on the east lead into the first and third row of bays respectively. Twenty-six windows along the walls illuminate the bright interior.

The prayer hall is seven aisles wide and six bays deep. The central aisle, running from the main portal on the north side to the mihrab on the south, is wider than the three aisles on each side. A total of twenty-eight freestanding piers carry the roof structure, capped by a hipped roof on the exterior.

A large bay covered by a shallow wooden dome occupies the area in front of the central mihrab, one of three mihrabs on the qibla wall. This dome is carried on heavy arches and pendentives in contrast with the lighter substructure of the original dome. The two bays preceding the qibla dome are crowned by narrow barrel vault and a wide domical muqarnas vault with a hexagonal skylight. The remaining bays either have domes or barrel vaults. Most of these vaults collapsed in 1964 and re-built in the following years. 

The minaret, which rises on a stone base at the northwest corner of the mosque, is entered from the interior, from stairs along the north wall of the mosque. The shaft with the spiral stairs begins just above the top of the mosque walls. 

The mosque is made of cut stone, with timber used in the construction of the domes. The minaret shaft is made of bricks. The interior is decorated with geometric motifs that are common to mosques of the twelfth century. The wide rectangular frame of the simple stalactite mihrab niche is carved in high relief with a braided pattern composed of intersecting octagons. Individual stones carved in this manner were used in repairing the inner arch of the main portal. Carved molding was found in various parts of the mosque, but has mostly disappeared over time. 

Sinclair, T. A. Eastern Turkey: an architectural and archaeological survey, 202-203. London: Pindar Press, 1989.