Торжественное открытие Благородного собрания состоялось 2 декабря 1841 года. Вот как кратко описывает его в своих мемуарах Бларамберг, который был участником этого события: «Организовали запись, по которой каждый член общества согласно своему состоянию должен был внести средства, и в течение недели было собрано 10 тыс. рублей ассигнациями ― сумма для Оренбурга того времени значительная. Поистине блестящий бал состоялся 2 декабря в залах Дворянского собрания; такого бала оренбуржцы еще никогда не устраивали; Блестящие мундиры, богатые туалеты, музыка, обслуживание и ужин были не хуже, чем в Петербурге, и генерал-адьютант Перовский, за здоровье которого было выпито много шампанского, был очень тронут привязанностью своих подчиненных и почитателей, а также восхищен любезностью множества женщин и девушек, среди которых было много красавиц». Таким образом, цвет тогдашнего оренбургского общества отпраздновал, выражаясь по-современному, ввод в эксплуатацию этого дома. Самой значительной стройкой того времени был комплекс Караван-Сарая. Это было первым строительством такого размаха вне стен крепости. Караван-Сарай строился как место для пристанища башкир, для укрепления связи с ними, для налаживания более тесного контакта, но делалось это не только ради башкир, а в гораздо более широких целях.

В те годы правительство стремилось привлечь на сторону России народы Средней Азии, исповедывавшие ислам. В большой степени это стимулировалось необходимостью противостоять проискам Великобритании в этом районе. Одной из мер привлечения среднеазиатских народов было проявление заботы о своих подданных мусульманах.

Башкирия тогда была связана с Оренбургом в военно-административном отношении, имелось башкиро-мещеряцкое войско, и башкирам часто приходилось приезжать по делам в Оренбург. В. А. Перовский, хорошо понимавший важность налаживания максимально хороших отношений с ними, решил, что в Оренбурге необходимо иметь для них хорошее пристанище, которое одновременно служило бы усилению хозяйственно-экономических и культурных связей с Башкирией. Получив одобрение вышестоящих инстанций, военный губернатор обратился в апреле 1836 года к кантональным начальникам (Башкирия делилась на кантоны). Он писал, что намерен «приступить к построению общественного постоялого двора, или караван-сарая, в котором могли бы останавливаться со всеми удобствами каждый башкир и мещеряк без всякой платы». Строительство должно было вестись на деньги башкиро-мещеряцкого войска, но собирались и пожертвования.

В своей работе «Караван-сарай в Оренбурге» архитектор Б. Г. Калимуллин, касаясь проекта комплекса, пишет, что он был одновременно поручен двум авторам: «строителю Казанского университета М. Коринфскому и выдающемуся петербургскому архитектору А. Брюллову», проект первого был отвергнут из-за ряда недостатков. То есть фактически состоялся конкурс. Это указание вызывает сомнение, такому заключению противоречит содержание и датировка писем В. А. Перовского А.П. Брюллову, с которым военный губернатор был в большой дружбе.

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

Через месяц Александр Брюллов получил другое письмо, датированное 3 ноября 1836 года, где Перовский пишет, что с тех пор как он послал первое письмо с просьбой и программой «на построение в Оренбурге башкирской военной канцелярии и проч.» он несколько изменил условия: «...я подумал, ― пишет губернатор, ― что было бы безсовестно стеснять твой талант в подобном предприятии, назначая ему число сажен, на которых он имеет право развернуться. Я решил этот дом строить за городом; места ― сколько душе угодно; одного только не теряй из виду: мечеть должна быть по означенному на плане направлению. Материалы здесь дешевы, но чрезвычайно дороги рабочие и особенно мастера; в этом отношении прошу тебя соблюсти возможную экономию. Если б ты потрудился дело устроить так, чтобы в бытность мою в Петербурге мог я представить план государю в начале января, то я бы тебя от всей души поцеловал точно так, как теперь обнимаю. В. Перовский». Из этих писем ясно видно, что сначала собирались строить караван-сарай внутри крепости, что, естественно, должно было значительно ограничить площадь. А. П. Брюллов выполнил просьбу друга, и 19 января 1837 года проект был утвержден.

В конце мая 1837 года В. А. Перовский передал материалы на постройку караван-сарая старшему корпусному инженеру в Оренбурге. Время между январем и маем ушло, вероятно, на доработку деталей проекта и т. п. Военный губернатор писал: «...постройку эту поручить в искусственном и хозяйственном отношении инженер-поручику Сенькову. При надзоре... за правильностью, прочностью и чистотою в отделке будет находиться Уральскаго войска архитектор 14-го класса Гопиус». Как видно из последней фразы, Гопиус был больше в Оренбурге, чем в Уральске. Работал он впрочем добросовестно и хорошо, уже в 1832 году войсковая канцелярия представляла его к награде. К этому ходатайству на следующий год присоединился Перовский. В 1835 году Гопиус был награжден орденом Станислава 4-й степени и в 1837 году произведен в 12-й класс. Работы начались, очевидно, летом этого же года. К ним, как пишет Б. Г. Калимуллин в упомянутой работе, для изготовления строительных материалов и их транспортировки, а также к разным подсобным работам привлекались главным образом башкиры и мещеряки, «в сооружении же зданий и их оформлении участвовали строители и других национальностей, в первую очередь русские мастера».

К началу 1842 года внешне комплекс выглядел завершенным. Часть помещений основного корпуса была готова еще раньше, так как в декабре 1841 года на втором этаже уже разместилась канцелярия командующего башкиро-мещеряцким войском. Тогда Караван-Сарай производил несколько иное эмоциональное воздействие, потому что и окружение и масштабность были иными, по отношению к окружающей местности комплекс был выше, чем сейчас.

Интересен выбор места. Хотя город был еще крепостью и вопрос о ее упразднении не стоял, Караван-Сарай явно поставлен в расчете на то, что рано или поздно крепости не будет, город расширится и минарет мечети будет выполнять определенную градообразующую роль: он поставлен точно в створе Введенской улицы в этом легко убедиться, посмотрев сейчас, особенно после опадания листвы, вдоль улицы 9-го Января. Видимо, решая вопрос о месте комплекса, строители считали, что потомки выведут улицу прямо на Караван-Сарай; но так, к сожалению, не случилось.

В августе 1846 года состоялось торжественное открытие Караван-Сарая. По существу-то открывали мечеть, которая вместе с минаретом является центром композиции; отделка ее, вероятно, и заняла все то время, ведь мастеров было очень мало.