Хотя в XVIII веке Россия имела виды на Северный Кавказ – богатые территории с плоским рельефом и черноземной почвой к северу от Кубани и Терека, – он, как и казахское степное приграничье, оставался срединной землей, где проживало множество местных этнических групп, а притязания России на господство поддерживали в лучшем случае только казаки. Уже в XVI веке степи севернее Терека и долина этой реки были местом обитания казаков, промышлявших воровством и грабежами и служивших России тогда, когда им было удобно. Среди них встречались турки, персы, беглые украинские и русские крестьяне, дагестанцы, калмыки, грузины, армяне, ингуши, осетины. Из верований в ходу были анимизм, ислам, православие (нового и старого обрядов, а также грузинского толка). Центром казачьих земель являлся основанный в 1588 году Терский город, который номинально считался русской крепостью и в конце XVI столетия насчитывал, вероятно, около 20 тысяч жителей – преимущественно представителей местных народностей; казаков и русских было намного меньше. В XVI веке Россия начала заключать союзы с кавказскими государствами – Иван IV в 1561 году вступил в брак с кабардинской княжной, – а царский титул с 1594 года содержал слова: «Государь Иверские земли, Грузинских Царей, и Кабардинския земли, Черкаских и Горских Князей». Однако номинальное русское присутствие в Терском городе мало что давало в смысле реального господства.
Серьезное внимание на Северный Кавказ Россия обратила во время Персидских походов Петра I, вступив в борьбу за влияние в этой области с крымскими татарами и Османской империей, и на протяжении большей части XVIII века стремилась закрепиться там. Были основаны Кизлярская и Моздокская крепости с гарнизонами, составленными из местных казаков и из разного рода пришлых. В 1720-е годы тысяче семей донских казаков было велено переселиться на Северный Кавказ (вероятно, последняя из мер такого рода, принятых после подавления Булавинского восстания 1707–1708 годов). Кизляр стал центром для нескольких групп, собирательно именовавшихся терскими казаками. В 1721 году они, как и все остальные казаки в империи, были переданы в ведение Военной коллегии, но в то время Россия еще не утвердилась здесь как следует.
Российское господство стало более ощутимым в 1760-е годы, после успехов в войнах с турками и сооружения укрепленных линий против набегов чеченцев и кабардинцев. В 1760–1780-е годы была построена Кавказская линия, протянувшаяся от Азова к юго-востоку – до Ставрополя и Моздока на Тереке, далее вдоль левого берега Терека к Кизляру, расположенному близ впадения реки в Каспий. В целом линия описывала полукруг, проходя через весь Северный Кавказ. В 1794 году появилась новая линия, параллельная Азовско-Кизлярской: от Екатеринограда близ Моздока (западнее него) к Керченскому проливу. Для охраны этих линий в 1790-е годы на Кавказ переместили часть казаков из распущенного Запорожского войска; так возникло Черноморское казачье войско, располагавшееся севернее реки Кубань. Ногайцы, рассеявшиеся по причерноморским степям, также вступали в казачьи отряды на Северном Кавказе и на Дону. Все эти казаки несли гарнизонную службу, защищали русские территории от нападения, использовались в качестве посыльных и конвойных, составляли карты, строили дороги и мосты.
Их присутствие давало стабильность, необходимую для притока крестьян, которые, в свою очередь, обеспечивали тыл для воинских частей и укрепляли позиции империи в этих краях. В 1760-х годах Россия стала привлекать сюда осетин, предоставив им налоговые льготы в случае обращения в православие, а в 1780-х переселила около 68 тысяч государственных крестьян, преимущественно однодворцев. Помимо насильственного переселения, происходило и добровольное: на Кавказ устремлялись беглые крестьяне, староверы и многочисленные представители северокавказских этнических групп: Томас Баррет назвал это «великой перетасовкой кавказских народностей». Армяне, грузины, ингуши, осетины, чеченцы поселялись за русскими укрепленными линиями, чтобы заниматься землепашеством, выращивать виноград и шелковицу, вести торговлю.