При Перовском же начали строиться казенные каменные здания; оборонительные казармы около Преображенской церкви, дом благородного собрания на месте развалившегося здания главного народного училища, ордонанс-гауз, квартира плац-майора и комендантское управление, а рядом с ним дом коменданта. Ныне первый занят ремесленным училищем, а последний квартирою одного из командиров баталионов, расположенных в Оренбурге.
В то же время построен генерал-губернаторский дом, но Перовский не переходил в него; первым поместился в нем генерал Обручев.
Частных каменных домов в первое управление Перовского было два: один — ныне занятый аптекой Герштейна, а другой — квартирой Тургайского губернатора. Оба дома принадлежали купцу Осоргину, впоследствии разорившемуся, и были проданы один в частные руки, а другой в казну за долги.
Дом Еникуцева на Николаевской улице, где ныне контрольная палата, был вчерне построен в 1838 — 39 г., но не занимался владельцами по суеверному предрассудку, что новый дом потребует покойника, а их было двое — муж и жена.
В 1852 г. дом этот куплен был для канцелярии генерал-губернатора, и поверье сбылось: с переходом канцелярии и появлением в доме жильцов умер самый старый из них — Зверев, старик 80 лет, хорошо помнивший времена князя Волконского и генерала Бахметева.
Караван-Сарай был начат постройкою Перовским чрез оповещение циркулярами башкирских кантонных начальников для объявления народу, что здание строится для приезжающих в Оренбург по своим делам башкир, останавливавшихся ранее в частных домах, а с постройкою караван-сарая будут иметь более удобное помещение для себя и своих лошадей. Здание в начале было построено с большими комнатами в виде казарм, с нарами, а в нижнем этаже конюшни. Все показывает, что Перовский думал перенести на русскую землю азиатские караван сараи для странствующих мусульман и торговцев; в этих видах он положил построить среди здания мечеть, чтобы живущие в караван-сарае башкиры имели полную возможность исполнять по своему закону требы и молитвы; этим желали показать народу, что правительство далеко от мысли насильственными мерами обращать магометан в христианство, каковые слухи тайно распространяли казанские татары, известные фанатики, а напротив, правительство строит на свои средства мечеть и не простую, а превосходящую все известные в крае мечети. С этою целью приглашали башкир делать пожертвования для украшения новой мечети. Для сбора последних был послан дер. Нижней Чебеньки ахун Абдулла Давлетшин, родом татарин, приписанный в башкирское войско. Он собрал до 30 т. руб. асс.
Для освещения в здании мечети повешена дорогая люстра, купленная в Петербурге в английском магазине. К завершению всего построен каменный высокий минарет, облицованный снаружи белыми изразцами.
В конце 1841 г. в караван-сарай перевели канцелярию командующего башкирским войском и дали квартиры чиновникам и команде башкир в 50 человек, посылаемых для несения службы.
Помещения для башкир не думали открывать и никто из них никогда там не останавливался. Обращение здания в постоялый двор стоило бы дорого по отоплению, содержанию в чистоте и ремонту. Правый фасад здания, где были казармы с нарами, переделали под помещение канцелярии, а левый обратили в помещение для губернатора; в нижнем этаже, где были стойла для лошадей, оставшиеся своды показывают первое его назначение.
Для открытия мечети был приглашен муфтий и до 300 человек магометан; кроме того, было множество любопытных, прибывших без всякого приглашения.