In 1556 Russia conquered the Astrakhan Khanate on the north shore of the Caspian Sea. The surrounding area was held by the Nogai Horde.To the east of the Nogais were the Kazakhs and to the north, between the Volga and Urals, were the Bashkirs. Around this time some free Cossacks had established themselves on the Ural River. In 1602 they captured Konye-Urgench in Khivan territory. Returning laden with loot they were surrounded by the Khivans and slaughtered. A second expedition lost its way in the snow, starved, and the few survivors were enslaved by the Khivans. There seems to have been a third expedition which is ill-documented.

At the time of Peter the Great there was a major push southeast. In addition to the Irtysh expeditions above there was the disastrous 1717 attempt to conquer Khiva. Following the Russo-Persian War (1722–1723) Russia briefly occupied the west side of the Caspian Sea.

About 1734 another move was planned, which provoked the Bashkir War (1735–1740). Once Bashkiria was pacified, Russia's southeastern frontier was the Orenburg line roughly between the Urals and the Caspian Sea.

The Siberian line: By the late eighteenth century Russia held a line of forts roughly along the current Kazakhstan border, which is approximately the boundary between forest and steppe. For reference these forts (and foundation dates) were:

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

Uralsk was an old settlement of free Cossacks. Orenburg, Orsk and Troitsk were founded as a result of the Bashkir War about 1740 and this section was called the Orenburg line. Orenburg was long the base from which Russia watched and tried to control the Kazakh steppe. The four eastern forts were along the Irtysh River. After China conquered Xinjiang in 1759 both empires had a few border posts near the current border.