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

Здание, в котором расположен музей, было построено в 1856 году по приказу Василия Алексеевича Перовского (в этот период - оренбургского и самарского генерал-губернатора) в стиле "неоготика" (ранее "псевдоготика") для хранения губернского архива и казны. Место для постройки определилось тем, что ранее здесь была денежная кладовая с погребом. Из архивных источников известно, что подряд на строительные работы выполнял Иван Петрович Скалочкин – талантливый крепостной архитектор-самоучка.

В 1856 году строительство здания было завершено. На его башне были установлены часы «таможенного ведомства», ранее находившиеся на Гостином дворе в Оренбурге.

Позднее здание приспособили под главную гауптвахту, которая существовала здесь до 1974 года.

По указу властей в 1930-х годах часы-куранты с башни гауптвахты были перевезены в Самару для строящегося здания окружного Дома офицеров.

В 1978 году по инициативе председателя Оренбургского горисполкома Юрия Дмитриевича Гаранькина здание было передано городу. После нескольких лет реставрационных работ 30 апреля 1983 года в нем был открыт отдел досоветской истории Оренбургского областного краеведческого музея. Одновременно с реставрацией здания были восстановлены часы на башне по чертежам талантливого оренбургского часовщика Николая Степановича Кузнецова.

В 1987 году здание музея было поставлено на учет как памятник архитектуры (Решение исполкома Оренбургского областного Совета народных депутатов №179 от 13.05.87г.). В 1989 году статус музея изменился - он перестал был филиалом Областного музея и обрел самостоятельность, а в 1995 году здание Музея истории Оренбурга было включено в список памятников архитектуры федерального значения (Указ Президента РФ №17 от 20.02.95 г.).

Музейный фонд Музея истории Оренбурга отражает богатство истории и культуры города, своеобразие городского быта, историю и культуру различных национальностей, проживающих в Оренбурге и Оренбургской области.

В основном фонде Музея истории Оренбурга насчитывается более 8000 единиц. В составе основного фонда есть интересные предметы этнографии (башкирская, казахская, мордовская национальная одежда, украшения), материалы, рассказывающие о выдающихся представителях культуры России, внёсших значительный вклад в развитие Оренбургского края и страны (личные вещи и фотографии поэта Ю.С.Энтина, Народной артистки СССР Л.П.Филатовой, Народного артиста РСФСР В.А.Борцова и др.).

Общая экспозиционная площадь МБУ "Музей истории Оренбурга" составляет 1 671 квадратный метр, в год музей и его подразделения посещают около 40 тысяч человек.