Происхождение Шамхальского и ряда других дагестанских владений хроника «Дербенд-намэ» («Сказание о Дербенте») описывает следующим образом:
«Его высочество Мюслиме(арабский завоеватель Абу-Муслим - Авт.),
устроив дела города Дербента, предпринял поход против кумыков. Кумыки вышли навстречу ему, но после нескольких сражений покорились и приняли исламизм. Его высочество соорудил джума-мечети(главные или пятничные мечети)
в городе кумыков(Тарки - Лет.)
для вновь обращенных мусульман, назначил Шахбала, сына Абяуллы, сына Абаса, правителем и начальником страны и дал ему кадия для сообщения народу правил ислама, после чего он сам обратился против каракайтагов. Племена каракайтагов изготовились к войне, но после многих сражений, происшедших в различных местах, большая часть каракайтагов искала спасения своего в покорности и обращении в исламизм… При его высочестве находился один из его родственников, по имени Эмир Хемзе; его высочество назначил его начальником над каракайтагами, и от него происходят нынешние уцмии (так называются государи) каракайтагов. Большую часть жителей Табасарани вначале составляли евреи и неверные. Сначала они тоже не хотели покориться, но после того, как его высочество истребил и взял в плен значительное число их, остальные обратились в мусульманскую веру. В войске его высочества находился добродетельный и набожный человек по имени Мехмед-Масум; его он назначил правителем над обитателями Табасарани и дал ему двух кадиев затем, чтобы они обучали правилам ислама. Отдал он строгое приказание, чтобы с тех пор во всех важных случаях жители Табасарани следовали наставлениям Масума и двух кадиев, и чтобы Масум (Майсум), кадии, Эмир-Хемзе и все племена Дагестана, от Грузии до Дешти-Кипчак, находились в повиновении у Шахбала, правителя кумыков. От этого Шахбала происходят нынешние шамхалы».
Происхождение титула шамхалов приписывают тому, что преемников Шахбала стали величать этим же именем, и впоследствии оно трансформировалось в слово «шамхал». Другие исследователи полагают, что слово «шамхал» происходит от названий провинции Шам и местечка Хал в Сирии, откуда был родом Шахбал. Мирза Казембек, ученый-востоковед, в примечании к «Дербенд-намэ» писал, что Шам - древнее название Сирии, откуда арабские халифы посылали правителей в Дагестан, а слово «хал» означает «князь».
Шамхальство Тарковское с конца XVIII века находилось под российским протекторатом. В 1806 году Мсхти-шамхал (1794-1830) получил во владение Улусский магал (9 деревень), принадлежавший мятежному Ших-Али-хану Дербентскому. В 1818 году командующий Отдельным Кавказским корпусом генерал от инфантерии А. П. Ермолов отстранил от власти участника противостоявшей ему коалиции дагестанских владетелей Гасан-хана Мехтулинского и его земли присоединил к шамхальству Тарковскому.
С этой целью был издан соответствующий акт:
«Господину генерал-лейтенанту, высокостепенному и высокопочетному Мехти-Шамхалу Тарковскому, Вали Дагестанскому.