Башкирия тогда была связана с Оренбургом в военно-административном отношении, имелось башкиро-мещеряцкое войско, и башкирам часто приходилось приезжать по делам в Оренбург. В. А. Перовский, хорошо понимавший важность налаживания максимально хороших отношений с ними, решил, что в Оренбурге необходимо иметь для них хорошее пристанище, которое одновременно служило бы усилению хозяйственно-экономических и культурных связей с Башкирией. Получив одобрение вышестоящих инстанций, военный губернатор обратился в апреле 1836 года к кантональным начальникам (Башкирия делилась на кантоны). Он писал, что намерен «приступить к построению общественного постоялого двора, или караван-сарая, в котором могли бы останавливаться со всеми удобствами каждый башкир и мещеряк без всякой платы». Строительство должно было вестись на деньги башкиро-мещеряцкого войска, но собирались и пожертвования.
В своей работе «Караван-сарай в Оренбурге» архитектор Б. Г. Калимуллин, касаясь проекта комплекса, пишет, что он был одновременно поручен двум авторам: «строителю Казанского университета М. Коринфскому и выдающемуся петербургскому архитектору А. Брюллову», проект первого был отвергнут из-за ряда недостатков. То есть фактически состоялся конкурс. Это указание вызывает сомнение, такому заключению противоречит содержание и датировка писем В. А. Перовского А.П. Брюллову, с которым военный губернатор был в большой дружбе.
Первое письмо написано 6 октября 1836 года, то есть почти через полгода после обращения к начальникам кантонов. В. А. Перовский не стал бы медлить с заказом. Очевидно, заказ был сделан сначала М. Коринфскому, а уже после рассмотрения его проекта ― Брюллову. Кроме того, если бы заказ был сделан сразу обоим архитекторам, губернатор упомянул бы об этом в письме, а в нем ничего похожего нет. Вот его текст: «Любезнейший Александр! Вспомни старую дружбу нашу и займись, пожалуйста, без отлагательства составлением проекта по предлагаемой программе. Я затеял строить здесь караван-сарай; это дело меня весьма интересует. Хочется начать с наступлением весны; ради Бога, не мешкай. Я уверен твердо в твоем знании и вкусе, но крепко сомневаюсь в прилежании: ты мне обещал много, да сдержал мало. Не в поощрение тебе, а просто к сведению, скажу тебе, что постройка караван-сарая есть затея не моя частная, а казенная, а потому труды по составлению сметы, перечерчению планов и проч. будут вознаграждены по-надлежащему. Задача довольно трудная, быть может, по ограниченности места, но если бы сажени слишком стесняли твое зодческое воображение, то делай как знаешь, а я постараюсь приискать место по твоему плану. Обнимаю тебя. Можешь ли ты приготовить дело в шесть недель после получения этого письма? Ты бы меня обязал чрезвычайно. Душевно тебе преданный Василий Перовский». В комментариях этот текст не нуждается.
Через месяц Александр Брюллов получил другое письмо, датированное 3 ноября 1836 года, где Перовский пишет, что с тех пор как он послал первое письмо с просьбой и программой «на построение в Оренбурге башкирской военной канцелярии и проч.» он несколько изменил условия: «...я подумал, ― пишет губернатор, ― что было бы безсовестно стеснять твой талант в подобном предприятии, назначая ему число сажен, на которых он имеет право развернуться. Я решил этот дом строить за городом; места ― сколько душе угодно; одного только не теряй из виду: мечеть должна быть по означенному на плане направлению. Материалы здесь дешевы, но чрезвычайно дороги рабочие и особенно мастера; в этом отношении прошу тебя соблюсти возможную экономию. Если б ты потрудился дело устроить так, чтобы в бытность мою в Петербурге мог я представить план государю в начале января, то я бы тебя от всей души поцеловал точно так, как теперь обнимаю. В. Перовский». Из этих писем ясно видно, что сначала собирались строить караван-сарай внутри крепости, что, естественно, должно было значительно ограничить площадь. А. П. Брюллов выполнил просьбу друга, и 19 января 1837 года проект был утвержден.