Для построения этого города отправился тот же Кириллов в чине статского советника и скоро должен был столкнуться с знаменитым правителем горных заводов Татищевым. Осенью Татищев донес в Кабинет, что, будучи в Башкирии, говорил он татарам, что быть там ярмарке. Татары очень обрадовались, но Татищев стал им внушать, что нельзя ограничиваться этою ярмаркою: много лошадей в Сибири купить некому, а можно бы им продать их у Макарья или в Москве. Татары отвечали, что пригонять им лошадей никак нельзя, потому что везде поля засеваются хлебом, офицеры же, присылаемые к ним для покупки лошадей по деревням, делают им великие обиды, если же они, татары, «попротивятся, хотя и правильно», то берут их на Уфу и сильно их разоряют. Татищев представлял, чтоб учредить ярмарку в Уфимском уезде при реке Белой, ниже Бирска, куда купечество со всей России может приезжать; сверх того, устроить там хлебный магазин; там же можно будет покупать недорого илецкую соль, лучшую в России, хотя только про обиход императрицы. Татищев прибавлял, что татары везде его спрашивали, скоро ли переменят нынешнего уфимского воеводу Кошелева, потому что он великий грабитель и бить челом на него не смеют. Вследствие этого представления Татищева Кабинет послал указ Кириллову об учреждении ярмарки в Уфимском уезде на реке Белой; кроме того, он должен был подлиннее наведаться о поведении Кошелева и немедленно отписать в Кабинет. Кириллов отвечал, что лошадиную ярмарку учредить и в обычай ввести никак нельзя, потому что башкирец дожидается купцов к себе в дом, а в город поедет разве по приказной нужде или для гулянья. О Кошелеве дал отзыв неблагоприятный. В Кабинете отдали это дело на усмотрение Кириллова.
Между тем Кириллов, готовясь к построению Оренбурга, жил в Уфе и посылал в Кабинет любопытные известия о стране. Донося в Кабинет о вражде между киргизами и башкирами, он писал: «Никогда не следует допускать их в согласие, а в потребном случае надобно нарочно поднимать их друг на друга и тем смирять».