Проект Кирилова был одобрен Сенатом, и 1 мая 1734 года дана «всемилостивейшая апробация», где говорилось о постройке города на Ори, обеспечении строительства рабочей силой, финансировании экспедиции, включении войсковых подразделений и т.д. Последний пункт гласил: «ко отправлению выше изложенных всех дел определить обер-секретаря Ивана Кирилова и с ним быть мурзе Алексею Тевкелеву, которых туда отправить немедленно и дать полную инструкцию и указы, а сколько каких людей надобно отсюда и из Москвы, о том донесть». Подробная инструкция, включавшая и устройство пристани на Аральском море, была дана 18 мая. В тот же день Кирилов был пожалован в статские советники, а Тевкелев произведен в полковники. Одновременно Кирилов получил указ о больших полномочиях, беспрекословном выполнении всеми военными и должностными лицами его приказов и оказание ему всяческого содействия. В довершение будущему городу 7 июня Анной была подписана «Привилегия», скрепленная также подписями А. Остермана, П. Ягужинского, князя А. Черкасского. Именно в этот день город получил официально свое имя.

Необходимо сказать несколько слов о происхождении названия города. Толкование урбонима Оренбург вызывало споры с самого начала. Принято выводить его от реки Орь, на этом настаивал и П. И. Рычков[3]. Однако выведение названия Оренбург только от первичного топонима Орь не совсем убедительно. Слово составлено по продуктивной тогда модели, где вторым компонентом является немецкое «бург». В первой же части оказывается два лишних звука (ен) или по крайней мере один (н), то есть должно быть Орьбург, или правильнее даже Орбург, поскольку название этой реки сначала писалось с твердым знаком. Сочетание (рб) не выходит за нормы языка (например, верба). Можно допустить и Оребург, даже Орибург, но наличие «и», совершенно необъяснимо, если исходить из вышеупомянутого толкования. Если же учесть, что Оръ ассоциируется с немецким Ор ― ухо и что в годы царствования Анны иностранцы имели значительное политическое влияние, а город должен был стать форпостом, состав слова становится ясен: множественное число от Ор-Орен+бург, в полном соответствии с правилами немецкого словообразования. Должно быть, первичный топоним составил основу, а сходство с немецким определило форму «Оренбург». Таким образом, этимология урбонима Оренбург представляется имеющей двойственную основу.

В задачи экспедиции, которую сначала в целях обеспечения секретности назвали не Оренбургской, а «известной», входило не только основание главного города, крепостей и других пунктов для защиты юго-восточной границы, почти 200 лет до того остававшейся почти открытой. Она должна была исследовать и описать малоизученные территории Южного Урала, казахской степи, их природные богатства, изучить историю, культуру, обычаи живших там народов. Одной из областей, на которую прежде всего обращалось внимание экспедиции, был Урал с его полезными ископаемыми, судоходными реками, лесными богатствами, где следовало наметить места основания заводов.

В числе главных практических целей было налаживание торговли с азиатскими народами, и в конечном итоге подготовка включения Средней Азии в состав Российской империи. Но независимо от целей, которые ставил царизм, проникновение в Среднюю Азию и освоение территории огромного края, занимавшего в 1758 году около двух миллионов квадратных километров, было по отношению к народам, которые населяли эти земли, явлением прогрессивным. Это отмечал Ф. Энгельс, говоря, что «Россия действительно играет прогрессивную роль по отношению к Востоку» [4] .

Основная часть экспедиции во главе с Кириловым отправилась из Петербурга уже 15 июня, сначала водным путем. Остальные выехали на две недели позже. В Москве, куда Кирилов прибыл 29 июня, экспедиция была доукомплектована. Всего набралось около 200 человек. В нее вошли военные, инженеры, геодезисты, моряки и судовые мастера, канцеляристы, переводчик, художник, историограф и ботаник, бергпробир, хирург, аптекарь, несколько студентов Славяно-греко-латинской академии. На должность бухгалтера экспедиции назначили Петра Ивановича Рычкова, ставшего позже крупным разносторонним ученым, первым членом-корреспондентом Петербургской Академии наук.

Из Москвы экспедиция отправилась водным путем в Казань и оттуда в Уфу, куда Кирилов, ехавший сухим путем, и прибыл 10 ноября. Здесь остановились зимовать, готовясь к весеннему походу, сюда прибывали и войска. Экспедиции были приданы 10 рот Пензенского полка, 3 роты формируемых оренбургских драгун и иррегулярные войска, среди которых было 150 уфимских и 100 яицких казаков. Всего насчитывалось более 2500 человек.

В апреле 1735 года «известная экспедиция» выступила из Уфы к устью Ори. Путь ее лежал на юг вверх по долине реки Белой, затем вниз к урочищу Красная гора на Яике и отсюда вверх по его течению к устью орскому. На место прибыли лишь 6 августа, пройдя путь около 700 верст. Такое медленное продвижение объясняется задержками из-за поднятого башкирскими феодалами восстания. Они не хотели основания города и строительства крепостей, так как видели в упрочении русской администрации на юго-востоке страны угрозу своим привилегиям.

После соответствующей подготовки 15 августа 1735 года была заложена небольшая крепость недалеко от устья. Об этом событии в Сенат рапортовали: «Августа 15-го Оренбургская первая крепость купно с цитаделью малою на горе Преображенской заложена и следует работа с поспешностью». Крепость была «о четырех бастионах» незначительных размеров: 145 на 120 саженей, не считая выступов по бастионам, что в метрах составляет 309 и 256 соответственно. Вместе с цитаделью с севера на юг ее протяженность была немногим более полукилометра. Со словом «цитадель» связано представление о чем-то мощном, неприступном, здесь же ничего подобного не было. Оградой цитадели служила небольшая насыпь с частоколом общей высотой около двух метров. В крепости было двое ворот: на север, в сторону Яика, и на запад. 30 августа в нее уже ввели солдатскую команду, а на следующее утро установили артиллерию. Это, разумеется, не значит, что за такой короткий срок все было закончено. Ров, например, далеко не достигал проектного профиля, во многих местах его не было совсем; крепостная ограда носила временный характер. Поспешность диктовалась необходимостью: до зимы оставалось мало времени, и надо было иметь хоть какой-то оплот.

31 августа, то есть в тот же день, когда утром в первой крепости установили артиллерию, «при Яике и устье Орском» торжественно заложили «настоящий Оренбург о девяти бастионах по ситуации места регулярно при выстреле из тридцати одной пушки», ― пишет П. И. Рычков. Расстояние от его центра до первой крепости составляло около двух километров, диаметр равнялся почти километру. Планировка решена по радиально-кольцевой схеме с центральной площадью, что вполне соответствовало господствовавшему принципу регулярности. В церемонии закладки принимали участие киргиз-кайсаки Младшего и Среднего жузов, башкиры и другие. Присутствовал сын Абулхаира султан Ералы, были также купцы из Ташкента. И. К. Кирилов пригласил азиатских и российских купцов на следующий год на торг в новый город Оренбург. Таким образом, сразу выявились обе основных функции города: быть оплотом новой пограничной линии крепостей, которую начинали создавать, и служить центром хозяйственнополитического общения с Востоком. Расположение города на левом берегу Яика подчеркивало, что крепость должна служить защитой казахам.

Постройку девятибастионного города-крепости отложили до следующего года, чтобы первую крепость «возможным образом утвердить». На следующий год помешало разраставшееся восстание в Башкирии. Так «настоящий Оренбург» никогда и не был начат постройкой на Ори, поскольку инициатор этого дела И. К. Кирилов вскоре, 14 апреля 1737 года, умер.