В связи с этими событиями Кирилов подготовил и представил (в 1733 году) проекты по обеспечению безопасности новых подданных России и всей российской юго-западной границы, а также по установлению прочных торговых связей с Индией и странами Средней Азии. Для достижения этих целей он предложил соорудить новую русскую крепость в устье реки Ори, притока Яика (теперь река Урал), а для быстрейшего заселения нового города — разрешить всем русским, бухарским, хивинским, ташкентским, индийским и другим купцам свободно селиться в нем; чтобы казахи, каракалпаки и башкиры свободно посещали город, — отвести в нем каждому народу особые слободы и дома, построенные в соответствии с их нравами и обычаями, возвести в городе каменные мечети, открыть школы и специальные дома для приема приезжающих в город ханов.
В 1734 году Кирилов подал в Сенат еще один документ — о новых подданных России, казахах и каракалпаках. Он выразил надежду, что наконец прекратятся набеги казахов на русские границы и на караваны русских купцов, направлявшиеся в страны Средней Азии. В качестве гарантии миролюбия новых российских подданных необходимо, по его мнению, сооружение не только города-крепости на реке Ори, но и ряда крепостей по рекам Лику и Самаре. Город на Ори необходим и «для отворения свободного с товарами пути в Бухары, в Водокшан, в Балх и Индию». Путь через эту крепость и через владения казахов и каракалпаков будет более надежным и безопасным, нежели путь в Индию через Астрахань, Хиву и Бухару. Эти новые крепости и военные укрепления помогут обеспечить спокойствие и в башкирских землях. Для хозяйственного освоения природных богатств в Башкирии следует развивать добычу илецкой соли, слюды, разработку месторождений медных и железных руд.
Проекты Кирилова 1 мая 1734 года получили одобрение правительства и императрицы, а самому ему было поручено организовать специальную экспедицию и, возглавив ее, отправиться в Башкирию для выполнения всех предложенных мероприятий. Кирилов был произведен в чин статского советника с окладом 3 тысячи рублей в год. По врученной ему инструкции он должен был построить в устье реки Ори город-крепость и привлечь туда как можно больше русских и иностранных купцов, ремесленников. Сразу по завершении строительства города предписывалось отправить «малый караван с товарами прямо в Бухарию и куда можно далее». Кроме того, ему поручалось организовать поиск месторождений золота, серебра и других полезных ископаемых в башкирских, киргиз-кайсацких (казахских) и каракалпакских владениях.
Статский советник немедленно приступил к организации экспедиции. Он наметил включить в ее состав офицеров армии и флота, военных инженеров, геодезистов, архитектора, математика-астронома, ботаника, священника, переводчика, канцелярских работников, боцманов, матросов, капралов, солдат, рабочих; 75 человек нашлись в Петербурге, остальные — в Москве.
Указом от 7 июня 1734 года новому городу, который планировали построить в устье реки Ори, присвоили наименование Оренбург и предоставили его будущим жителям широкие привилегии. Подлинник указа, завернутый в парчу с золотыми кистями и шнурами, был вложен в серебряный и вызолоченный ковчег, который 15 июня Кирилову вручила сама императрица во время данной ему по этому поводу аудиенции. В тот же день он выехал в Москву. Через две недели Петербург покинул экспедиционный отряд во главе с поручиком П. С. Бахметевым.
Упорно добивался Кирилов назначения в экспедицию «ученого священника». Ему сообщили 2 сентября 1734 года, что в ее состав определен представленный из московской Славяно-греко-латинской академии «к посвящению в попы школы риторики ученик Михайло Ломоносов». Кирилов, вероятно, познакомился с учеником, так как сообщил в Синодального правления канцелярию, что «тем школьником по произведению его во священство будет он доволен». Но через два дня кандидатура Ломоносова отпала, так как тот сознался: он не сын холмогорского попа, как называл себя вначале, а сын крестьянина. В экспедицию согласился отправиться ученый священник одной из московских церквей Антипа Мартианов Лямин.
Кирилов планировал открыть в Оренбурге школу, и поэтому, помимо научных книг по астрономии, математике, физике, химии, медицине, натуральной истории (то есть по зоологии, ботанике и минералогии), горному делу и истории, он включил в библиотеку экспедиции учебники: немецкие, французские и латинские азбуки, «книги риторические, исторические и поэтические», а также экземпляры Библии на немецком, французском и латинском языках.
Удалось добиться, чтобы с 1735 года в экспедиции участвовал хороший знаток математики и астрономии английский капитан Джон Эльтон (соленое озеро на востоке Волгоградской области носит его имя; оно было описано им и стало источником пищевой соли). В составе экспедиции оказались 10 лучших геодезистов, ботаник и художник, а также рудознатцы.