Генеалогия, представленная самими Салтукидами в надгробных надписях, называет в качестве одного из их предков некоего Абу ль-Касима, хотя нельзя быть полностью уверенным, что человек с таким именем – одним из имен пророка Мухаммеда – вообще существовал или обладал какой-либо властью. Первый известный нам Салтукид – это Али, о котором сказано, что он был правителем Эрзурума в 1103 году, когда приехал, чтобы поступить на службу к султану Махаммаду, сыну Мелик-шаха, который, потерпев поражение, нашел убежище в Ахлате. Возможно, что несколькими годами ранее о нем писал армянский летописец Мхитар Айриванкский, однако хронология этой записи весьма туманна. Но в любом случае в 1123 году он был известен латинскому хроникеру Ордерику Виталию как союзник Артукида Балака, которому он отправил нескольких пленных франков. Однако двумя годами ранее, когда другой Артукид, Ильгази, заключил с несколькими князьями союз против грузин и пришел в Эрзурум, историки этой экспедиции не называют его имени. Возможно, он уехал или был просто одним из вассалов султана Тогрула из Аррана (северо-запад Азербайджана). Что верно, определить невозможно.
С другой стороны, принципиально важно, что в борьбе с грузинами упоминается имя его сына и наследника Салтука, который, должно быть, вскоре после 1123 года стал его преемником. У него была дочь или сестра, которая после 1130 года вышла замуж за Шах-и-Армина (царя Армении) из Ахлата, Сукмана II. В 1153 или 1154, а потом в 1156 году во время волнений в Ани, бывшей армянской столице, теперь находившейся в руках сельджуков, Салтуку пришлось вмешаться на стороне мусульманской династии, которая оказалась под угрозой изгнания со стороны местных христиан и грузин. Он был взят в плен, но его выкупила княгиня Ахлата. В 1164 году Сельджукид из Румского султаната, Кылыч-Арслан, желая заключить с ним союз против Данишмендида Яга-базана, попросил руки одной из его дочерей, но по дороге она была схвачена Ягы-базаном, который насильно выдал ее замуж за своего племянника Зу-л-Нуна. По словам его современника Ибн аль-Азрака, Салтук умер в Раджабе в мае 1168 года. Если судить по монетам, отчеканенным им самим и его сыном Мухаммедом (другие аспекты этих монет мы обсудим позже), складывается впечатление, что эти князья номинально продолжали хранить верность не Сельджукидам Румского (Иконийского) султаната, а представителям династии Сельджукидов из Ирана, даже после того, как те пришли в упадок. Это не единственное время, когда Эрзурум, похоже, был теснее связан с иранским, а не с «румским» миром.
О сыне Салтука Мухаммеде известно только то, что в конце своего правления он вступил в сношения с грузинами. Его сын аль-Музаффар Мелик-шах, как и несколько других соседей, задумал жениться на юной грузинской царице Тамар, даже несмотря на то, что это означало отречься от ислама. После того как он был принят ею соответствующим образом, но затем получил отказ, ему в качестве утешения отдали незаконнорожденную «принцессу крови». Этот эпизод не смог надолго исправить отношения между соседями. Давид – муж, которого выбрала себе Тамар, напал и разграбил Эрзурум. В 1189 году отвергнутый жених стал преемником своего отца, но царствовал лишь недолгое время, поскольку с 1197 года (593 год Хиджры) его сменил сын, Ала ад-Дин Абу Мансур, последний из династии, кто предшествовал описанным ниже событиям. Мухаммед построил Большую мечеть в Эрзуруме. Абу Мансур ее украсил. В надписи, которая, по обычаю, увековечила это событие, он дал себе такие чисто мусульманские высокие титулы, как «усмиритель еретиков», «украшение паломничества» и «царь греков и армян Диярбакыра и Диярраби».
О династии Мангуджакидов известно несколько больше. Самые ранние упоминания о фамильном эпониме Мангуджак восходят не к битве при Манцикерте, как полагали более поздние не склонные к критике генеалогисты, а к 1118 году, когда он, находясь в Камахе, угрожал Малатье. Оказавшись перед лицом мести со стороны Сельджукидов из Малатьи и его наставника Артукида Балака из Харперта, он, как было указано ранее, отправился за помощью к правителю Трабзона (Трапезунда) Гаврасу. Несмотря на то что он вместе с Артукидом потерпел поражение от Гавраса, объединившегося с Данишмендидом Гумуштегином, ему все же удалось остаться на свободе и избежать наказания, поскольку он был зятем Гумуштегина. Однако за этим эпизодом следует такая глухая тишина в летописях всех времен и народов, что остается только признать, что это княжество не являлось сценой каких-то впечатляющих событий. В него входили такие города, как Эрзинджан, Шебинкарахисар (Кугуния) и Дивриги, являвшиеся основными центрами, а также Камах и другие важные крепости. Генеалогисты более поздних князей пишут, что его сыном и наследником был Исхак, который поделил его территории между Сулейманом (Дивриги) и Даудом (Эрзинджан и вся северная часть). С той единственной оговоркой, что эпиграфические следы оставила только ветвь из Дивриги, которая в любом случае оказалась более активной в деле строительства.