В конце мая 1837 года В. А. Перовский передал материалы на постройку караван-сарая старшему корпусному инженеру в Оренбурге. Время между январем и маем ушло, вероятно, на доработку деталей проекта и т. п. Военный губернатор писал: «...постройку эту поручить в искусственном и хозяйственном отношении инженер-поручику Сенькову. При надзоре... за правильностью, прочностью и чистотою в отделке будет находиться Уральскаго войска архитектор 14-го класса Гопиус». Как видно из последней фразы, Гопиус был больше в Оренбурге, чем в Уральске. Работал он впрочем добросовестно и хорошо, уже в 1832 году войсковая канцелярия представляла его к награде. К этому ходатайству на следующий год присоединился Перовский. В 1835 году Гопиус был награжден орденом Станислава 4-й степени и в 1837 году произведен в 12-й класс. Работы начались, очевидно, летом этого же года. К ним, как пишет Б. Г. Калимуллин в упомянутой работе, для изготовления строительных материалов и их транспортировки, а также к разным подсобным работам привлекались главным образом башкиры и мещеряки, «в сооружении же зданий и их оформлении участвовали строители и других национальностей, в первую очередь русские мастера».
К началу 1842 года внешне комплекс выглядел завершенным. Часть помещений основного корпуса была готова еще раньше, так как в декабре 1841 года на втором этаже уже разместилась канцелярия командующего башкиро-мещеряцким войском. Тогда Караван-Сарай производил несколько иное эмоциональное воздействие, потому что и окружение и масштабность были иными, по отношению к окружающей местности комплекс был выше, чем сейчас.
Интересен выбор места. Хотя город был еще крепостью и вопрос о ее упразднении не стоял, Караван-Сарай явно поставлен в расчете на то, что рано или поздно крепости не будет, город расширится и минарет мечети будет выполнять определенную градообразующую роль: он поставлен точно в створе Введенской улицы в этом легко убедиться, посмотрев сейчас, особенно после опадания листвы, вдоль улицы 9-го Января. Видимо, решая вопрос о месте комплекса, строители считали, что потомки выведут улицу прямо на Караван-Сарай; но так, к сожалению, не случилось.
В августе 1846 года состоялось торжественное открытие Караван-Сарая. По существу-то открывали мечеть, которая вместе с минаретом является центром композиции; отделка ее, вероятно, и заняла все то время, ведь мастеров было очень мало.
О достоинствах и особенностях Караван-Сарая хорошо и подробно рассказал в своей работе архитектор Барый Гибатович Калимуллин. Он выделяет как самое главное и наиболее ценное ансамблевое качество «соразмерность отдельных частей комплекса, стройность общего силуэта, согласованность всей композиции». По формам здания сильно отличаются, но они соподчинены и дополняют друг друга. Хорошо сказано о развитии композиции в высоту: «С низких, горизонтально протяженных стен хозяйственных пристроев взгляд переходит к стенам основного здания, и угловым башенкам над крышей, следует выше к куполу мечети, затем поднимается к минарету, его конусному завершению, шпилю и, наконец, уходит в необъятный простор неба».
Анализируя архитектурный образ Караван-Сарая, Б.Г. Калимуллин приходит к заключению, что в нем отражена схема летнего башкирского аула. Ассоциацию с аулом усиливают возвышающиеся над крышей угловые башенки, которые напоминают легкие летние юрты. До нас Караван-Сарай дошел с рядом изменений. Так, хозяйственный пристрой потерял свои первоначально четкие формы из-за добавления разновысоких построек, минарет соединен с мечетью чуждым ансамблю переходом.
Кроме таких выдающихся в отношении архитектуры зданий, строились и скромные, имевшие чисто практическое значение, например, казенное лесопильное и мукомольное заведение, большая оборонительная казарма вместо куртины между Успенским бастионом и Преображенским полубастионом, и другие. Кое-что осталось лишь в проектах. Не лишена интереса история так и не построенного постоянного моста через Урал. Необходимость его была очевидна, сообщение с Бухарской стороной, как почти сто лет до этого, осуществлялось посредством «моста на судах» ― летом, и паромной переправы ― осенью и весной, зимой же, разумеется, по льду. Нормальное сообщение, таким образом, нарушалось не только весной, но и осенью во время ледостава. Поэтому весной 1838 года В. А. Перовский специально для строительства водопровода и моста (каменного или деревянного на каменных опорах) просил департамент путей сообщения прислать знающего инженера, сообщая, что в «Оренбургской губернии ныне находится один только офицер Корпуса путей сообщения ― поручик Сергеев, занятый безотлучно на вновь прокладываемом промышленном пути». Просьбу удовлетворили, и в августе того же года в Оренбург прибыл полковник Зеге фон Лауренберг, до этого строивший мост между Ригой и Митавой[46]. 19 ноября он уже рапортует о представлении проектов и смет. Мост проектировался «о семи арках шириною по 8 сажен 5 футов каждая», а по обоим берегам должны были устраиваться земляные насыпи с мостами и трубами для протока весенних вод. Место для моста выбрали чуть пониже, чем стоит нынешний автогужевой. Документы послали в Комиссию проектов и смет, которая в своем заключении от 28 января 1839 года указала, что необходимо еще тщательно изучить течение реки, его скорость, особенно в половодье и т. д. Работы на строительстве моста были, однако, начаты задолго до получения ответа комиссии. За 37 рабочих дней, начиная с 14 декабря 1838 и по 12 февраля 1839, сделали довольно много той работы, которую можно, и даже лучше, производить зимой, ― забили трехсаженные сваи, которые должны были служить опорой для быков. Забивались они почти на всю длину плотными группами рядом друг с другом. За это время вбили 194 сваи, 160 заострили и насадили железные колпаки. Основной рабочей силой были арестанты. В этот период, например, у копров на забивке свай их работало немногим более 70 человек, а при них 16 конвойных под командой двух-трех унтер-офицеров. Из вольных людей ежедневно ― 4 или 5 плотников, которым платили по тем временам довольно много по «частной цене»: в день по полтора рубля. Остальным платили гораздо меньше, все они были ведь на казенном довольствии: арестант получал в день по 10, конвойный ― по 5, а унтер-офицер ― по 20 копеек.