Музей располагается в двухэтажном деревянном особняке К. П. и А. К. Слотовых с мезонином в г. Уфе. Дом является историко-архитектурным памятником.

В 1923 году Правительство республики подарило дом Народному комиссару внутренних дел республики — Шагиту Ахметовичу Худайбердину и его семье. Шагит Ахметович прожил в доме один год, его жена и дочь — вплоть до 1960 года.

Открытие музея планировалось в 1959 году, когда семья Худайбердиных хотела отдать дом для открытия экспозиции в честь Ш. Худайбердина. В 1961 году в дом переехала детская библиотека № 7, которая в 1990 году переехала на улицу Мингажева. В 1991 году решено отдать дом под музей.

Первоначально планировалось создание мемориального музея Ш. Худайбердина. В дальнейшем решено было назвать музей его именем и оставить в экспозиции мемориальную комнату Ш. Худайбердина, а в двух залах показать основные вехи национально-государственного строительства Республики Башкортостан.

В музее показаны процессы национально-государственного строительства в Башкортостане от истоков до сегодняшних событий, материалы и документы о создании и становлении национальной государственности башкирского народа начиная с момента формирования башкирского национального движения; различные проекты национально-государственного устройства Башкортостана: Временного революционного совета Башкортостана, Татаро-Башкирской советской республики, Урало-Волжских штатов, Башкиро-Киргизской республики; рассказывается о роли центральных органов Советской власти и лидеров башкирского национального движения А-З. Валидова, Ш. Манатова, М. Халикова и др. в создании башкирской автономии; территориальные изменения, а также административные деления Башкортостана; достижения и неудачи, допущенные в ходе проведения национально-государственного строительства в Башкортостане.

До недавнего времени обретение национальной автономии башкирского народа связывалось только с победой Октябрьской революции и Соглашением от 23 марта 1919 года. В то же время башкирское национальное движение, борьба башкир за свою государственность и свободу в 1917—1919 гг. игнорировались в угоду господствующей тогда идеологии.

Переосмысление многих событий того времени стало возможным сегодня благодаря доступности архивных документов, легализации трудов лидера башкирского национального движения А.-З. Валиди.

Отдельный зал музея — это мемориальная комната Ш. Худайбердина.

Отдельный зал посвящён участникам войн в Афганистане и Чечне.

Экспозиция третьего зала посвящена народной артистке БАССР Тамаре Худайбердиной — дочери Ш. Худайбердина.