In 1556 veroverde Rusland de Astrachan Khanate aan de noordkust van de Kaspische Zee. Het omliggende gebied was in handen van de Nogai Horde. Ten oosten van de Nogais lagen de Kazachen en in het noorden, tussen de Wolga en de Oeral, de Bashkirs. Rond deze tijd hadden enkele vrije Kozakken zich gevestigd aan de rivier de Oeral. In 1602 veroverden ze Konye-Urgench op het grondgebied van Khivan. Toen ze beladen met buit terugkeerden, werden ze omsingeld door de Khivans en afgeslacht. Een tweede expeditie verdwaalde in de sneeuw, hongerde uit, en de weinige overlevenden werden tot slaaf gemaakt door de Khivans. Er lijkt een derde expeditie te zijn geweest die slecht gedocumenteerd is.

Ten tijde van Peter de Grote was er een grote opmars naar het zuidoosten. Naast de Irtysh-expedities hierboven was er de rampzalige poging uit 1717 om Khiva te veroveren. Na de Russisch- Perzische oorlog (1722-1723) bezette Rusland korte tijd de westkant van de Kaspische Zee.

Omstreeks 1734 werd een nieuwe stap gepland, die de Basjkiersoorlog (1735–1740) uitlokte. Toen Bashkiria eenmaal gepacificeerd was, lag de zuidoostelijke grens van Rusland de Orenburg-lijn, grofweg tussen de Oeral en de Kaspische Zee.

De Siberische linie: Tegen het einde van de achttiende eeuw bezat Rusland een linie van forten, ruwweg langs de huidige grens met Kazachstan, die ongeveer de grens vormt tussen bos en steppe. Ter referentie: deze forten (en stichtingsdata) waren:

Guryev (1645), Oeralsk (1613), Orenburg (1743), Orsk (1735). Troitsk (1743), Petropavlovsk (1753), Omsk (1716), Pavlodar (1720), Semipalitinsk (1718) Ust-Kamenogorsk (1720).

Uralsk was een oude nederzetting van vrije Kozakken. Orenburg, Orsk en Troitsk werden gesticht als gevolg van de Basjkiersoorlog rond 1740 en dit gedeelte werd de Orenburglinie genoemd. Orenburg was lange tijd de basis van waaruit Rusland toekeken en probeerde de Kazachse steppe onder controle te krijgen. De vier oostelijke forten lagen langs de rivier de Irtysh. NadatChina Xinjiang in 1759 had veroverd, hadden beide rijken enkele grensposten nabij de huidige grens.