The large area in the south east of the Russian Empire was often referred to as the Wild Fields, unsuitable for settlement or industrial use.
In 1730 the Khan of the Lesser Horde sent the Russian government a request that his people be accepted as Russian subjects. In February 1731 Empress Anna Ioannovna signed a charter recognizing the Lesser Horde’s voluntary accession to the Russian Empire. 

Shortly afterwards, Ivan Kirillovich Kirilov developed a proposal entitled A Declaration on the Kirghiz-Kaisak and Karakalpak Hordes, in which he emphasized the importance of organizing a special expedition. This scholar made it his mission to describe the Kazakh and Karakalpak steppes, beginning with their geography and mineral resources, and ending with a study of the trade routes in the region and the opportunities they offered for economic cooperation with other nations. Ivan Kirilov proposed the construction of a fortified town at the mouth of the river Or, and a chain of fortifications along the river Yaik and other rivers, as a frontier.

On August 15 (August 26, New Style) 1735 the construction of the fortress of Orenburg, the future center of Orenburg Guberniya, was begun at a site on the left bank of the River Yaik, to the east of its confluence with the River Or, and on the border between the Burzyansk and Kipchak districts of Ufa Province and the Kazakh steppes.

In December 1735 Ivan Kirilov went to Saint-Petersburg to present his plans for the conquest of Bashkiria, and was able to convince the Empress Anna Ioannovna to approve his plan to use Cossack forces to suppress the revolt of the Bashkirs. Strong measures were required as Baskirs had several times attacked the fort while it was being constructed, causing the deaths of many Russian settlers and preventing the development of the Guberniya. He would dedicate the rest of his life to achieving this goal.

Because of the flooding of the rivers, in 1739 it was decided to begin the construction of a new town of the same name further downstream on the River Yaik. But the construction of this new town never began, as the new site turned out to be unsuitable for construction: there were no trees, the ground was rocky and it was too far from the river.

On April 19 (April 30, New Style) 1743 the construction of Orenburg began again, for the third time, on the site of the former Berdsk fortress, more than 200 km from the original location.

The fortress which was, for a while, known as the First Orenburg was preserved, and in August 1741 it was renamed Orsk (an Order stating that “the Former Orenburg shall be renamed Orsk fortress” was issued on August 20 1739) and in time it became the main fortress in the Orsk section of the Orenburg Lines, commanding five other fortresses and nine redoubts.

In 1738, half a verst from Orsk fortress Vasily Nikitich Tatishchev, the new head of the Orenburg expedition, built a commodities exchange, on the site now occupied by the Old Town market. From 1746 the fortress started to lose its importance as a trading centre, as the commodities exchange developed, but the trade routes to Khiva and Bukhara, and the route from the Zaural region to Orenburg still passed through it.