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