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