Статский советник немедленно приступил к организации экспедиции. Он наметил включить в ее состав офицеров армии и флота, военных инженеров, геодезистов, архитектора, математика-астронома, ботаника, священника, переводчика, канцелярских работников, боцманов, матросов, капралов, солдат, рабочих; 75 человек нашлись в Петербурге, остальные — в Москве.

Указом от 7 июня 1734 года новому городу, который планировали построить в устье реки Ори, присвоили наименование Оренбург и предоставили его будущим жителям широкие привилегии. Подлинник указа, завернутый в парчу с золотыми кистями и шнурами, был вложен в серебряный и вызолоченный ковчег, который 15 июня Кирилову вручила сама императрица во время данной ему по этому поводу аудиенции. В тот же день он выехал в Москву. Через две недели Петербург покинул экспедиционный отряд во главе с поручиком П. С. Бахметевым.

Упорно добивался Кирилов назначения в экспедицию «ученого священника». Ему сообщили 2 сентября 1734 года, что в ее состав определен представленный из московской Славяно-греко-латинской академии «к посвящению в попы школы риторики ученик Михайло Ломоносов». Кирилов, вероятно, познакомился с учеником, так как сообщил в Синодального правления канцелярию, что «тем школьником по произведению его во священство будет он доволен». Но через два дня кандидатура Ломоносова отпала, так как тот сознался: он не сын холмогорского попа, как называл себя вначале, а сын крестьянина. В экспедицию согласился отправиться ученый священник одной из московских церквей Антипа Мартианов Лямин.

Кирилов планировал открыть в Оренбурге школу, и поэтому, помимо научных книг по астрономии, математике, физике, химии, медицине, натуральной истории (то есть по зоологии, ботанике и минералогии), горному делу и истории, он включил в библиотеку экспедиции учебники: немецкие, французские и латинские азбуки, «книги риторические, исторические и поэтические», а также экземпляры Библии на немецком, французском и латинском языках.

Удалось добиться, чтобы с 1735 года в экспедиции участвовал хороший знаток математики и астрономии английский капитан Джон Эльтон (соленое озеро на востоке Волгоградской области носит его имя; оно было описано им и стало источником пищевой соли). В составе экспедиции оказались 10 лучших геодезистов, ботаник и художник, а также рудознатцы.

В Москве все оборудование и запасы экспедиции были погружены на И судов, и 25 августа Кирилов отправился в Казань. Там, приняв Пензенский полк и артиллерию, он поехал в Уфу, куда прибыл 10 ноября 1734 года. Поход на реку Орь начался 11 апреля 1735 года. Кирилов имел в своем распоряжении 15 рот регулярных войск, 350 казаков, 600 вооруженных татар, 100 башкир и обоз с провиантом и артиллерийскими орудиями, предназначенными для новой крепости, в том числе 52 медные 5-фунтовые пушки, две пудовые гаубицы и две медные 32-фунтовые мортиры (в те времена калибр орудий выражался в артиллерийских фунтах, за такой фунт принимался вес чугунного сплошного ядра диаметром 2 дюйма, или 50,8 миллиметра). Вскоре к Кирилову присоединился и переданный ему Вологодский полк. Экспедиция шла длинным и тяжелым путем вдоль левого берега реки Белой до Яика. О существовании более короткого и легкого пути по долине реки Самары Кирилов узнал позже.

К устью Ори прибыли 6 августа 1735 года, а 15 августа уже заложили крепость «о девяти бастионах с цитаделью малою». На другой день руководитель отправил императрице поздравление с приобретением Новой России — новых российских земель. В этом поздравлении он доложил, что по дороге к реке Ори и на месте будущего города нашел признаки богатых медных и серебряных месторождений, а также камни — порфир, яшму и мрамор.

Постройка крепости 30 августа была закончена, и в ней разместились гарнизонные войска и артиллерия; 31 августа при троекратном салюте из пушек был заложен город Оренбург. В 1739 году его переименовали в Орскую крепость. После кончины Кирилова новый начальник Оренбургской экспедиции В. Н. Татищев посчитал, что устье реки Ори не подходит для расположения административного центра обширного края. В 1739 году название Оренбург было перенесено на крепость, поставленную на 193 километра ниже по Яику, а в 1743 году — построенную еще на 75 километров ниже и через год ставшую центром края. Здесь, у устья реки Сакмары, притока Яика, и расположен ныне Оренбург.

На границе Башкирии Кирилов построил до 20 крепостей по рекам Сакмаре, Яику, Белой и Уфе, лично выбирая места для них, и проложил сеть дорог общей длиной более 3 тысяч километров. Геодезисты Оренбургской комиссии под руководством Кирилова выполнили съемочные работы вдоль созданной укрепленной линии Самара — Оренбург — Екатеринбург, а также в Заволжье и Закамье, составили карты различных районов огромного края. Одна из них, карта рек Самары и Яика, давала первое представление о возвышенности Общий Сырт. К северу от реки Самары уже были нанесены «горы неравные» — первое указание на Бугульминско-Белебеевскую возвышенность.

В 1736 году составили сводную карту, охватившую пространство около 500 тысяч квадратных километров: от реки Волги (на участке Казань — Самара) на западе до реки Тобол на востоке, от линии Кунгур — Екатеринбург на севере до Оренбурга и Яика на юге. На этой карте впервые был намечен рельеф части Южного Урала, правильно нанесены реки Самара, Верхний и Средний Яик, часть Средней Камы с рекой Белой; впервые на восточном склоне Урала были обозначены верховья рек системы Тобола и многочисленные озера.

Кирилов понимал, что эта карта далека от совершенства, и организовал проведение новых съемок. В ночь с 14 на 15 апреля 1737 года он, с мая предыдущего года болевший туберкулезом, скончался в Самаре. Этот талантливый организатор и исследователь рано умер, не успев осуществить многие свои задумки, но и того, что им было сделано, достаточно, чтобы его имя осталось в истории нашей Родины, в истории российской науки первой половины XVIII века.

Весной 1719 года 33-летний капитан-поручик артиллерии Василий Никитич Татищев обратился к царю Петру I с письмом, в котором предлагал провести общее размежевание земель в России, чтобы исключить земельные споры между землевладельцами и усовершенствовать систему сбора налогов. В другом представлении на имя царя Татищев, в частности, предлагал свой способ, «како ландкарты, или чертежи земель, сочинять со объявлением угодий, то есть пашни, лесов, рек, озер, болот». Эти письма и встречи Татищева с царем закончились тем, что специальным объявлением в Сенате Татищев был определен к «землемерию всего государства и сочинению обстоятельной российской географии с ландкартами».

Василий Татищев энергично принялся выполнять сложное и новое для него задание. По требованию царя он подготовил подробный план работы. В связи с этим планом появился царский указ от 9 декабря 1720 года, по которому «велено обучившихся в здешней академии (Морской академии в Санкт-Петербурге) геодезии и географии послать в губернии для сочинения ландкарт». Это стало началом плодотворной деятельности Василия Никитовича Татищева по изучению и картированию российских просторов.

Почему же именно ему артиллерийскому офицеру поручили эту ответственную государственную работу? Выбор царя не был случайным. Василий Никитович принадлежал к древнему хотя и обедневшему дворянскому роду. Его придворная служба началась в 1693 году когда после рождения царевны Анны (дочери царя Ивана, брата Петра I по отцу, и царицы Прасковьи) он в возрасте 7 лет с десятилетним своим братом Иваном были пожалованы в стольники. Правда, придворная служба продолжалась лишь до кончины царя Ивана в 1696 году.