Однако 11 февраля 1820 года А. П. Ермолов восстановил Мехтулинское ханство, лежавшее к западу от Тарковского шамхальства, в прежних границах, с центром в селе Дженгутай. Владетелем был утвержден Ахмед-хан - сын отстраненного Гасан-хана. Для защиты своего союзника царское правительство заняло постоянными гарнизонами важнейшие стратегические пункты шамхальства. В 1820 году рядом с резиденцией шамхалов, городом Тарки, была построена крепость Бурная; в 1834 году в селе Темир-Хан-Шура - базовое укрепление. Предосторожность оказалась не лишней: в мае 1831 года новый шамхал, Сулейман-паша (1830-1836), бежал от своих восставших подданных в Бурную под защиту российских войск.
После смерти в начале 1836 года Сулейман-паши шамхалом был провозглашен третий сын покойного Мехти-шамхала, Абу-Муслим-хан (второй сын, Зубаир, умер еще раньше). За верную службу Абу-Муслим был произведен в полковники, затем в генерал-майоры, а в августе 1856 года, в честь коронации императора Александра II, - в генерал-лейтенанты и генерал-адъютанты царской свиты. Еще ранее, 21 декабря 1834 года, будущему шамхалу был пожалован титул князя Тарковского, который должен был наследовать старший из потомков мужского пола по прямой линии и праву первородства.
Последним владетельным шамхалом Тарковским был старший сын Абу-Муслима, князь Шамсудин-хан (1860-1867). 3 декабря 1863 года кавказский наместник и главнокомандующий Кавказской армией великий князь Михаил Николаевич Романов пожаловал Шамсудин-хану грамоту об утверждении его шамхалом Тарковским, с соизволением носить перо на шапке в знак шамхальского достоинства. При этом из его титулов были исключены звания валия Дагестанского (шамхалы уже не являлись главными феодальными владетелями в Стране гор) и владетеля Буйнакского (эта старинная резиденция шамхалов давно стала их семейной вотчиной). Шамхалы имели свой аппарат власти, состоявший из нескольких визирей, исполнявших обязанности советников и министров, назира (казначея), кадия, секретаря, военачальника и дворецкого. При шамхале состояла дружина профессиональных воинов-нукеров. В бекствах (бейликствах) система управления была проще. Однако уже в 30-х годах XIX века ко двору шамхала был приставлен русский офицер, следивший за отбыванием жителями шамхальства нарядов и повинностей в пользу войск, расположенных в Северном Дагестане. Со временем эти офицеры получили статус помощника шамхала по управлению владением. Согласно исторической записке о шамхалах Тарковских, составленной чиновниками Временной комиссии, «наряженной для определения личных и поземельных прав туземцев Темирханшуринского округа», в 1867 году отношения шамхала к населению, которое отбывало известные повинности, обусловливались:
а) в одних селениях правом землевладельца;
б) в других - правом правителя;
в) в третьих - тем и другим.
Вот какие виды повинностей зафиксированы в записке: