Мысль использовать присоединение Младшего жуза для развития торговых отношений, продвижения на юго-восток и закрепления этого рубежа России принадлежала обер-секретарю Сената Ивану Кирилловичу Кирилову. Выражая чаяния Петра Великого, Кирилов хотел проложить торговые пути к среднеазиатским и восточным рынкам. Через возглавлявшего ответное посольство в Орду переводчика коллегии иностранных дел А. И. Тевкелева (он же Кутлу Мухамед Мамешев) Кирилов внушил мысль о необходимости основания города на Яике хану Абулхаиру, и тот официально попросил об этом русское правительство. В своем проекте под названием «Изъяснение о киргиз-кайсацкой и Каракалпакской ордах» Кирилов обосновал необходимость организации экспедиции на Южный Урал и подробно изложил ее цели и задачи, одной из которых было строительство города при устье Ори. Он стремился показать его значение в развитии экономических и политических связей с Казахстаном, Средней Азией, Каракалпакией, Восточным Туркестаном и Индией. По его мнению, место, выбранное для города, было «во всем изобильное», и дорога к Аральскому морю и дальше более удобна и безопасна, чем хивинская дорога через Астрахань, которая использовалась для торговых связей.
Проект Кирилова был одобрен Сенатом, и 1 мая 1734 года дана «Всемилостивейшая апробация», где говорилось о постройке города на Ори, обеспечении строительства рабочей силой, финансировании экспедиции, включении войсковых подразделений. Будущему городу 7 июня Анна подписала «Привилегию». Именно в этот день город официально получил свое имя.
В задачи экспедиции, которую в целях обеспечения секретности сначала называли не Оренбургской, а «известной», входило не только основание главного города, крепостей и других пунктов для защиты юго-восточной границы. Она должна была основательно исследовать и описать малоизученные территории Южного Урала, казахской степи, их природные богатства, изучить историю, культуру, обычаи живших там народов. Одной из областей, на которую прежде всего обращалось внимание экспедиции, был Урал с его полезными ископаемыми, судоходными реками, лесными богатствами, где следовало наметить места основания заводов. Петербургская Академия наук снабдила экспедицию астрономическими приборами, микроскопами, хирургическими инструментами, а также книгами по вопросам астрономии, математики, медицины, химии, биологии, ботаники, горного дела, истории. Таким образом, ставились и широкие научные задачи.
Одной из главных практических целей было налаживание торговли с азиатскими народами, и в конечном итоге подготовка включения Средней Азии в состав Российской Империи. Но, независимо от этой колонизаторской цели, проникновение в Среднюю Азию и освоение территории огромного края, занимавшего в 1758 году около двух миллионов квадратных километров, было, тем не менее, по отношению к народам, населявшим эти земли, явлением прогрессивным. Эту роль России по отношению к Востоку отмечал Ф. Энгельс[2].
Основная часть экспедиции во главе с Кириловым выехала из Петербурга 15 июня 1734 года. В Москве, куда Кирилов прибыл 29 июня, экспедицию доукомплектовали нужными специалистами, в составе ее оказалось около двухсот человек. Экспедиции были приданы регулярные и иррегулярные войска. Всего набралось более двух тысяч пятисот человек. Далее путь лежал через Казань на Уфу.
Из Уфы Кирилов выступил в апреле 1735 года, и несмотря на целый ряд трудностей 15 августа недалеко от устья Ори вверх по течению Яика на его левом берегу была заложена крепость, о чем в Сенат рапортовали: «Августа 15-го Оренбургская первая крепость купно с цитаделью малою на горе Преображенской заложена и следует работа с поспешностью». Со дня закладки этой крепости и следует отсчитывать возраст Орска, так как город позже развился именно отсюда.
30 августа в крепость ввели солдатскую команду, а на следующее утро установили артиллерию. В тот же день, 31 августа, торжественно заложили «настоящий Оренбург о девяти бастионах... при выстрелах из тридцати одной пушки», — пишет П. И. Рычков, состоявший бухгалтером при экспедиции.