13 мая 1929 г. на заседании Политбюро ЦК ТНРП принято решение о создании краеведческого музея тувинского народа. При единогласном решении директором был назначен В.П. Ермолаев. Созданы три отдела: местный, революции и общеобразовательный
Академия наук СССР, многие музеи и выставочные комитеты приняли активное участие в комплектовании фондов для будущего музея в Туве. Государственный Эрмитаж и Русский музей передали в дар картины западно-европейских и русских художников, несколько скульптур, образцы старинного оружия, рыцарские доспехи. Зоологический музей Академии наук СССР — чучела птиц, млекопитающих, пресмыкающихся, морских беспозвоночных. Официальное открытие музея состоялось в августе 1930 года.
26 марта 1942 г. Указом Президиума Малого Хурала трудящихся ТНР Государственному музею присвоено имя Алдан-Маадыр.
После вхождения ТНР в состав СССР музей получил статус областного, с 1961 г. — республиканского. В 1956 г. по результатам Всероссийского конкурса музей был признан одним из лучших и награжден Дипломом I-ой степени,
В 1980 г. Тувинский республиканский краеведческий музей был награжден Почетной Грамотой Президиума Верховного Совета Тувинской АССР в связи с 50-летием со дня основания. В 1985 г. экспозиция зала «Тува в годы Великой Отечественной войны» была отмечена Дипломом 1 степени в смотре музеев РСФСР. Автор М.Б. Кенин-Лопсан.
2 ноября 2008 г. в новом здании музея состоялось открытие выставки «Сокровища Долины царей. Царский курган Аржаан- 2».
Музей неоднократно становился победителем в открытых конкурсах «Музей года. Южная Сибирь». В 2014 г. по результатам открытого творческого конкурса Всероссийской историко-литературной премии «Александр Невский» проект «Первый директор музея Владимир Петрович Ермолаев» стал номинантом специальной премии «Хранители»
По результатам работ 2016 — 2018 гг. Национальный музей РТ признан ведущим учреждением культуры России и включен в Национальный Реестр «Ведущие учреждения культуры России». В 2018 г. во время проведения Саммита министров обороны стран СНГ и Монголии в музее реализован художественно-выставочный проект «Несокрушимая и легендарная». В Год добровольца в России музей организовал совместно с ТРО Российского военно-исторического общества и Советом регионального отделения ДОСААФ России по Республике Тыва автопробег «Маршрут памяти: восстанию 60-ти Алдан Маадыр – 135 лет».
В 2019 г. директор музея К.А. Бичелдей признан лучшим руководителем культурного учреждения в республике. В настоящее время в музее работают два доктора и пять кандидатов наук.