Anadolu’da kurulan ilk Türk beyliklerinden biri olan Saltuklu Beyliği’nin kurucusu Saltuk Bey’in (Ebü’l-Kāsım İzzeddin Saltuk Bey) Malazgirt zaferinden önceki hayatı hakkında bilgi yoktur. Anadolu’nun fethinde büyük hizmetlerde bulunduğu için Kars, Pasinler, Oltu, Erzurum, Tortum, Tercan, İspir, Bayburt, Şebinkarahisar ve yöreleri veraset yoluyla çocuklarına intikal etmek üzere kendisine iktâ edilmiştir (464/1071). Beyliğin 472’de (1080) kurulduğu da ileri sürülür. Erzurum ve çevresinin Emîr Saltuk Bey’e iktâ edilmesi onun diğer beylerden daha önemli konumda olduğunu göstermektedir.
Emîr Saltuk Bey’in ölümüyle yerine oğlu Ali geçmiştir. İbnü’l-Esîr, 496 (1102-1103) yılı olaylarını anlatırken Ali’nin söz konusu tarihte beyliğin başında bulunduğunu söylediğine göre Saltuk Bey bu tarihten önce vefat etmiş olmalıdır.
Büyük Selçuklu Sultanı Berkyaruk ile kardeşi Gence Meliki Muhammed Tapar arasında 8 Cemâziyelâhir 496 (19 Mart 1103) tarihinde Hoy kapısında cereyan eden ve Muhammed Tapar’ın yenilgisiyle sonuçlanan savaşın ardından Muhammed Tapar Erciş’e, oradan da Sökmen el-Kutbî’nin hâkimiyetindeki Ahlat’a çekildiğinde yanında Sökmen el-Kutbî, Muhammed b. Yağısıyan ve Kızılarslan gibi emîrler vardı. Erzenürrûm Emîri Ali b. Saltuk da bu sırada Ahlat’ta Muhammed Tapar’a katıldı. Berkyaruk ile Muhammed Tapar arasında 497’de (1104) yapılan anlaşmanın ardından Muhammed Tapar Meyyâfârikīn’e giderken ona refakat eden emîrler içinde Ali b. Saltuk da bulunuyordu.