Вызывает сомнение то, что шамхал собирался подпасть в зависимость от России добровольно. Вероятнее всего, это было желание (предложение) заключить договор о мире (дружбе) и торговле. Подтверждают это и слова В. А. Потто, который пишет: «Но ни дани, ни подданства, мы не добились»(ПоттоВ. А. Два века Терского казачества (15771801 гг.). Ставрополь: «Кавказская библиотека», 1991. С. 21), «Жалобы кабардинских князей на беспрерывные разбои и грабежи шамхальцев вынудили его наконец в начале 1560 г. послать воеводу Черемисинова с войском и кабардинцами «воевать Тюмень и Шавкала» (Там же).
Это было по сути началом эпохи русско-кавказских войн. Впервые русские войска вторглись на территорию Дагестана- во владения шамхала Тарковского. «Видный воевода Ивана Грозного Черемисинов ходил из Астрахани морем на Тарки, взял город и заставил шамхала уйти в горы» (Кушева Е.Н.Русско-дагестанские отношения в ХVI-ХУIIвеках: Материалы научной сессии по истории народов Дагестана. ДФ АН СССР ИИЯЛ. Махачкала, 1954. С. 14; Полное собрание русских летописей. М., 1965. т. 29. С. 289).Но в ходе ряда кровопролитных жестоких сражений, завоевателям был дан серьезный отпор. Черемисинову пришлось отступить.
Однако город Тюмень, лежавший в низовьях Терека и являвшийся столицей Тюменского владения, граничавшегося с Шамхальством Тарковским, был занят русским гарнизоном, и Тюменское владение подпало под власть Москвы (Потто В. А. Указ. соч. С. 21). Поскольку отряд Черемисинова не выполнил главную задачу не пробился в Кабарду, можно считать, пишет И. М. Сигаури что первая российская военная экспедиция на Северный Кавказ закончилась провалом (Сигаури И. М.Очерки истории и государственного устройства чеченцев с древнейших времен. М.: «Русская жизнь», 1997. С. 231). В следующем 1561 году совершилось крупное событие в Кабарде, еще теснее связавшее ее с Московским государством. В этом году царь Иван Васильевич вступил в брак с дочерью князя Темрюка, известною красавицей Мариан или Гуаще. Брак состоялся в августе 1561 г., когда Мариан приняла православную веру, и митрополит всея Руси Макарий, нарек ей имя Мария Темрюковна (Потто В. А.Указ. соч. С. 21). Данный брак имел большое значение для тесного сближения Москвы с кабардинскими черкесами.
Темрюк стремился с помощью своего могущественного зятя Ивана Грозного усилить свое влияние не только в Кабарде, но и на всем Северном Кавказе и, стать способным противостоять самому сильному в то время феодалу в регионе Шамхалу Тарковскому. В 1562 году по просьбе Темрюка обратившемуся к Ивану Грозному выслать войска, к нему были отправлены русские дружины из Казани и Астрахани во главе с князем Григорием Плещеевым. «Темрюк со государскими людьми недругом своим недружбу довел и в свою волю привел, а воевал Татцкие земли близ Скиньских городков, и взяли три городка, город Мохан, город Енгирь, город Каван, и мирзу Те-ташку убили и многих людей побили И воевали их землю одиннадцатьдней"(Полное собрание русских летописей.. М., 1965. т. 29 С. 324).
В 1566 году в Москву прибыл шурин царя Ивана Грозного, князь Мамстрюк, сын Темрюка, и бил челом, чтобы государь повелел «для бережения их поставить на Тереке усть Сююнчи реки крепкий город», в котором находилось бы постоянное русское войско, могущее им оказать помощь и защиту в нужное время (Потто В. А.Указ. соч. С. 23).
В 1567 году состоялся очередной поход московских и кабардинских войск против шамхала Тарковского (Хронология истории Дагестана / Сост. Магомедов Р. М.Махачкала, 1959. С. 39).
В ходе происходивших сражений был убит и шамхал Будай. Несмотря на это, независимость шамхальства была сохранена. Но русские сумели закрепиться на левом берегу реки Терек, против устья Сунжи. Там возникла первая русская крепость. Как пишет В. А. Потто, это была первая попытка стать твердою ногою у далеких предгорий Кавказского хребта, на том историческом пути, который три века спустя привел Россию к безраздельному господству на всем пространстве Кавказского перешейка (Потто В. А.Указ. соч. С. 23.).
Ряд исследователей допускает, что первая российская крепость на Северном Кавказе была построена уже в 1563 году, а не в 1567 г. Приехавший в Крым из Черкасс в июле 1563 года Кулчук-Мурза говорил хану Девлет-Гирею, что царь Иван IV весной этого года прислал в Черкасы к Темрюку князю воевод своих «// воеводы де пришед к Темрюку князю город поставили, и Темрюк де в городе сел. (Юдин П. Первые русские города на Тереке // Терские ведомости. 1912. 221)