В 1556 году из Астрахани пришло известие, что правители Шемахи, Шевкал и Тюменского княжества прислали представителей с предложениями о мире и торговле, а на следующий год от шамхала и тюменского князя в Москву прибыло посольство с просьбой о подданстве и о защите. Посольство было принято, но отношения шамхала и тюменского князя с Россией в тот момент не сложились: царь как раз начал поддержку других своих подданных - кабардинских князей, воевавших с Дагестаном. В 1560 году воевода И. С. Черемисинов во главе отряда стрельцов и казаков вышел из Астрахани на судах и высадил десант у города Тарки на каспийском побережье, чем вынудил шамхала отступить в горы. На этом свою миссию помощи кабардинцам воевода Черемисинов счел завершенной, и, изломав несколько строений, русские войска вернулись в Астрахань.
Вскоре в одной из стычек шамхал был убит, его преемник почел за благо найти с Россией общий язык, в 1567 году прислав в Москву посла с просьбой защитить его от кабардинцев в обмен на подданство. Результатам переговоров стала постройка на территории, принадлежавшей шамхалу русской крепости. Крепость получила название Койсинского острога.
В конце XVIвека предпринималась попытка договориться с шамхалом об урегулировании пограничных споров и о приведении его к присяге на верность русскому царю. Однако шамхал условием своего участия в переговорах поставил снос Койсинского острога, что было для России совершенно неприемлемо. Другие дагестанские князья не разделяли точку зрения упрямого шамхала: в 1602 — 1603 годах вассалы шамкала, кафыркумукский князь Сурхай Тарковский и Султан-Махмуд Эндереевский за спиной сюзерена прислали в Москву посольство с просьбой принять их в русское подданство. В это же время между шамхалом и наследником престола Крым-шамхалом вспыхнула ссора, переросшая в настоящую войну, причем шамхал ориентировался в политике на Османскую империю, наследник же стоял на прорусских позициях. Его просьбы о поддержке вовремя совпали с необходимостью России закрепиться в Дагестане ввиду иранской опасности.
Военная экспедиция с этой целью осуществилась в 1604 —1605 годах, когда русская группировка под командованием И. М. Бутурлина практически без боя овладела Эндереей и Теплыми водами, основав опорный пункт на Турзлуке и принудив шамхала к бегству. В Тарках сразу же началось строительство новых укреплений, однако обосноваться надолго Бутурлин не смог: запертые в городе русские войска были окружены многочисленными силами султана, подкрепленными собственными отрядами шамхала и антирусски настроенных кабардинских князей. Оказавшись в критическом положении, Бутурлин пошел на переговоры с турецким пашой и смог договориться о сдаче города на почетных условиях. Однако паша проявил вероломство, и при отходе на север значительная часть русского войска была истреблена. Также были сожжены Сунженский и Койсинский остроги, и лишь Терский городок оказался для османов недосягаемым.
Уже в 1610 году тарковские правители Гирей и Ильдар Сурхаевы обратились к терскому воеводе с просьбой принять их от имени царя в русское подданство. Вместе с ними в верности Москве поклялись еще семь зависящих от них князей и мурз. Объяснение такой смены настроений было простое: Гирей просил разрешения кумыкским узденям и крестьянам, имеющим пропуск с его печатью, свободный проезд через русские владения в Кабарду и обратно. Связи с Кабардой имели для Гирея важное экономическое значение, и с их нарушением он лишался одного из источников своих доходов.
Посол Гирея Томулдук прибыл в Москву в конце 1614 года и официально подтвердил вступление своего патрона в русское подданство. Вместе с тарковским Гиреем в верности царю поклялись и другие князья со своими людьми. В это же время подданным Русского государства был признан и эндереевскии шамхал Султан-Махмуд, умудрившийся одновременно оставаться и подданным иранского шаха.
Такая раздвоенность стоила ему определенных потерь: в 1615 году терский гарнизон выступил против Султан-Махмуда, поддержав Тарковского Гирея, что навело эндереевского правителя на мысль срочно сделать окончательный выбор подданства и сделать его в пользу русских. Остался верен России и Гирей, не поддавшийся соблазну переметнуться на иранскую сторону.
С усилением Русского государства в покровительстве его оказался заинтересован и Кайтаг. Каитагский уцмий в 1616 году обязался верно служить России и пропускать через свои земли русских купцов, охраняя их от случайностей в пути. Взамен уцмий надеялся получить возможность посылать своих торговых людей в пределы Русского государства, что сулило ему изрядные доходы.
В том же году, находясь перед угрозой иранской интервенции, Ильдар Тарковский, шамхал Андий, Алибек Казыкумухский, уцмий Кайтагский, Султан-Махмуд Эндереевскии и другие князья, собравшись на съезд, заключили мир друг с другом и уговорили Султан-Махмуда принять русское подданство. В качестве гарантии верности русскому царю эндереевскии правитель должен был передать терскому воеводе заложника из своей семьи, причем горцы рассматривали этот шаг как нечто само собой разумеющееся. Тут же, на съезде, был избран и наследник шамхальского престола, которым стал Ильдар, а русские власти обещали Ильдару, что будут консультироваться с ним о принятии в русское подданство каждого из дагестанских князей. В 1616 году подданным царя стал эндереевскии князь Султан-Махмут, а на следующий год к царю Михаилу Федоровичу с подобными же просьбами обратились уцмий Кайтага, шамхал Андий и аварский хан. Русская популярность на Кавказе росла пропорционально военным успехам.
Сын Султан-Махмуда Айдемир явился в июле 1631 года в Терский городок и там договорился с воеводой о совместных действиях против крымского царевича Шагин-Гирея, на стороне которого выступали иранские силы. Присоединиться к совместным против крымчаков действиям русских и горцев собирался и аварский хан, приславший по этому поводу в Терский городок специальное письмо, о том же 1631 году кайтагский уцмий Рустам-хан отправил в Москву посла Шамсея с просьбой принять Кайтаг в свое подданство и позволить его людям свободно торговать в Русском государстве. Ради возможности торговли с русскими Рустам-хан отклонил настойчивые предложения о союзе, переданные ему иранским шахом через его ставленника Шагин-Гирея. Переговоры кайтагского посла в Москве завершились признанием русским правительством Рустам-хана в качестве своего подданного. В 1633 году в селении Башли уцмий подписал клятву русскому царю, а в 1635 году в Москву прибыло от него второе посольство, подтвердившее подданство и договорившееся о некоторых пограничных вопросах. Военное и экономическое превосходство России привело к тому, что большая часть территории Дагестана вошла в состав Русского государства.
К 1588 году в Терском городке существовала отдельная Окоцкая слобода, жители которой находились в русском подданстве. Современные исследователи отождествляют окочан (ококов) с частью ингушей, однако в русских источниках в ряде случаев также названы и чеченцы, в XVI—XVII веках существовавшие не как отдельный народ, а как ряд родовых объединений. Окоцкие князья служили и Ивану Грозному, и его сыну Федору Ивановичу, причем правитель окочан Ших-мурза со своими людьми участвовал практически во всех мероприятиях терской администрации. Кроме того, Ших-мурза неоднократно являлся посредником между русскими властями и горцами, что было высоко оценено русским царем в специальном послании: «Нам твоя прямая служба ведома...» Пример Ших-мурзы вдохновил другого ингушского князя — Султан-мурзу, стоявшего во главе военно-политического союза Ларе, контролировавшего Дарьяльское ущелье. О своем желании быть подобно Ших-мурзе принятым под покровительство русского царя Султан-мурза рассказал московским послам в Грузии, которых он сопровождал через свою территорию.
В 1595 году Ших-мурза погиб в столкновении с кумыкским князем Ахмат-ханом, а последний пытался утвердиться владетелем над окочанами. Чтобыизбежать этого, окочане побросали дома и землю и в полном составе перебрались в Терский городок сразу заметно увеличив его население. С тех пор они постоянно проживали в Окоцкой слободе оказывали гостеприимство другим северокавказцам по тем или иным причинам, бежавшим в русские пределы.
Следующим после Ших-мурзы правителем окочан стал Батай-мурза, отправившийся в 1605 году в Москву в обществе кабардинского князя Сунчалея Янглычева, а также в сопровождении своих людей. Как раз в это время на московском троне находился Лжедмитрий I, на прием к которому и угодили царские правители. Батай-мурза был тепло принят самозванцем, награжден богатыми подарками и признан главой над всеми окочанами. Батаю было позволено купить в Москве для себя и своих людей 16 комплектов стальных доспехов, весьма ценившихся в горских княжествах. Его люди также получили жалованье на правах русских подданных. Вернувшись домой, в Терский городок, Батай-мурза исправно нес службу до 1609 года, пока вдруг все не бросил и не бежал с семьей и несколькими приближенными в горы, где примкнул к эндереевскому Султан-Махмуту. Причиной более чем поспешного отъезда Батая стало его старое соперничество с Сунчалеем Янглычевым, которому удалось стать старшим над всем нерусским населением Терского городка. Через семь лет Батай снова принес присягу русскому царю и был принят в подданство, однако вернуться в Терский городок так и не решился.
В 1614—1621 годах терские окочане неоднократно бывали по служебным делам в Москве, осуществляя связи между столицей и кавказскими владениями, а также выполняли в окрестностях Терского городка различные (иногда секретные) поручения русского правительства, что не мешало им изредка вступать в столкновения с товарищами по оружию — терскими казаками (например, выступление стрельцов и казаков в 1616 г. против Султан-Махмута, скрывавшегося в окоцких селениях, или поход в чеченские горы в 1618 г.).