В 1925 году в Туве был организован кружок «урянховедения» — изучения тувинской истории. Участники собирали материалы для создания музея — рукописи старожилов, предметы старины, фотографии, утварь из буддистских монастырей-хурээ. Это стало основой собрания Тувинского государственного музея, открытого в 1930 году. Из фондов Эрмитажа и Русского музея были переданы экспонаты, собранные в ходе археологических экспедиций АН СССР. Для посетителей музей был открыт в августе 1930 года. В марте 1942 года Малый хурал ТНР присвоил музею имя «Алдан-Маадыр» — «Шестьдесят богатырей».
В 2008 году в Кызыле было сдано новое здание музея. Из федерального бюджета выделили деньги на оборудование специального хранилища с современной системой сигнализации, контролем температурно-влажностного режима. Это позволило открыть для всеобщего обозрения постоянную экспозицию «Сокровища Долины царей Тувы. Царский курган Аржаан-2».
В 2011 году музей получил Гран-при регионального конкурса «Музей года. Южная Сибирь — 2011» среди государственных музеев. Два года подряд, в 2011 и в 2012 годах, становился победителем в номинации «Выставочный проект. Южная Сибирь».
В сентябре 2014 года в рамках Дней культуры, посвященных столетию единения Тывы с Россией, в Государственном историческом музее будет открыта выставка «Тыва. Золото скифской эпохи» из фонда Национального музея Республика Тыва.
Самая важная экспозиция, ради которой некоторые специально прилетают в Кызыл, находится в отдельном помещении за мощной бронированной дверью. Попасть туда можно за дополнительную плату. В полутемном зале под пуленепробиваемым стеклом лежат древние сокровища: мужские и женские золотые украшения, застежки-фибулы, булавки, кинжалы и колчаны с тончайшей инкрустацией, вещи «звериного стиля», в том числе знаменитая «аржаанская пантера». Коллекцию сравнивают со шлимановским «кладом Приама» и Сибирской коллекцией Петра I из Эрмитажа.