В конце 50-х годов XVI столетия в Москву прибыли кабардинские послы с просьбой наказать правителя-шамхала Тарковского. Их просьба была встречена с пониманием. В 1559 году против шамхала было послано русское войско с Астрахани, к которому примкнули гребенские казаки и кабардинская конница. К сожалению, подробных сведений об этом походе не сохранилось, но есть данные, что он завершился успешно. Об этом свидетельствует то, что в 1559 году шамхал Тарковский помирился с кабардинцами и подал прошение о принятии его владений под русское подданство. (Это был первый военный акт Российского государства на Кавказе.)

Для защиты от крымцев тесть Ивана Грозного кабардинский князь Темрюк Идарович упросил московского царя поставить на их землях крепость с сильным гарнизоном. Для этого в 1567 году из Астрахани на Терек были посланы воеводы Андрей Семенович Бабичев и Петр Протасьев «с огненным боем и многими людьми». В результате этой экспедиции на левом берегу Терека против впадения в него горной реки Сунжи (в районе нынешней станицы Шелковской) по приказу астраханского воеводы Лукьяна Новосельцева была построена крепость Терская (городок Терки), которая условно отделила кабардинские земли от кумыцких. Службу в этой крепости и ее окрестностях несли преимущественно гребенские казаки и городовые стрельцы общей численностью до трех тысяч человек, которые официально числились на московской службе, но реально жили по собственным законам и обычаям, во многом сходным с обычаями соседних горских народов. В 1568 году, опять-таки по просьбе кабардинского князя Темрюка, против Ханкальского ущелья был построен Сунженский острог (позже на его месте была заложена крепость Грозная).

О том, какую политику вела русская администрация в контролируемых ею районах Северного Кавказа можно судить по такому факту. В 1577 году, во время очередной войны между Турцией и Персией, турецкий султан приказал крымскому хану послать войска в Дагестан на помощь находившимся там туркам. Начальник крымского отряда Алды-Гирей обратился к воеводе Терской крепости с просьбой пропустить его войска через территорию, контролируемую казаками. Разрешение было получено. Но казаки своевременно предупредили о нашествии дагестанских правителей, и крымцы были разгромлены в Дагестане, а на обратном пути – добиты гребенскими казаками.

Данный случай вызвал гнев турецкого султана. Он потребовал от Москвы ликвидации крепости на Тереке, угрожая походом на Астрахань. Чтобы избежать войны Иван Грозный в 1581 году отдал приказ о сносе Терской крепости и постройке новой ближе к побережью Каспийского моря. Новая крепость, построенная в 1588 году, сохранила прежнее название, но проживавшие в ней и в ее окрестностях казаки стали именоваться терскими.

Но и старая крепость также не умерла. Сохранившиеся оборонительные строения быстро заняли вольные казаки. И только когда эти строения обветшали от времени, казаки оставили крепость и расселились по станицам, но по-прежнему называя себя гребенскими казаками.

При сыне Грозного Федоре Ивановиче реально правивший страной боярин Борис Федорович Годунов вступил в переговоры с персами. Он попытался с их помощью вытеснить турок с Восточного Кавказа и распространить власть Москвы вдоль западного побережья Каспийского моря. Персы оказались сговорчивыми и обещали большую военную помощь. Кроме того, в это время в Москву поступают сведения от терского воеводы Андрея Ивановича Хворостынина о стремлении аварского хана принять подданство России. Это стало решающим аргументом для реализации разработанных в Москве планов военной экспедиции.