Хакасский национальный краеведческий музей, основанный на общественных началах в 1929 году при окружном отделе народного образования, статус государственного  получил на основании Постановления №16 от 29 июля 1931 года Президиума Хакасского областного исполнительного комитета «Об организации областного музея». Первым директором музея был биолог В.А. Рюмин. С момента возникновения музея особое внимание уделялось этнографии хакасов 19 века. Экспозиции Хакасского краеведческого музея были представлены тремя отделами: природы, истории и социалистического строительства.

В 30-х гг. 20 в. коллекции музея пополнились образцами полезных ископаемых, геологическую коллекцию передал музею профессор И.К. Баженов, учитель К.С. Тодышев - юрту в полном убранстве, финорганы передали 100 предметов церковной утвари и 25 томов церковного архива за 1811 - 1839 годы, а И.П. Комягин - знак отличия родового старосты 1822 года. Из Минусинского музея были переданы образцы полезных ископаемых, предметы этнографии хакасов конца 19 века, изделия Абаканского железоделательного завода, а также около 300 археологических предметов. С 1938 года Хакасский музей участвует в научно-исследовательских экспедициях, в ходе которых фонды музея пополнились археологическими и этнографическими материалами.

С завершением строительства областного Дома культуры музею выделили 3 комнаты общей площадью 140 кв. м. В 1939 году музей возглавил приглашенный из Ленинграда Петр Иванович Каралькин, перед которым стояла задача разработки широкой программы деятельности музея. Он сумел за короткое время обновить экспозиции и создать передвижную выставку «Хакасия за 10 лет». В годы Великой Отечественной войны музей вынужден был свернуть экспозиции и освободить помещения для воинской части.

Хакасский областной музей возобновил работу в конце 1942 года, когда вместо убывшего на фронт Каралькина директором назначили эвакуированного из Ленинграда Александра Наумовича Савчука. Большую помощь музею оказали эвакуированные ученые: профессор С.А. Токарев, к.фил.н. Л.С. Шептаев, музыковед А.А. Кенель. С приходом в 1944 году Альберта Николаевича Липского музей возобновил участие в археологическом изучении области. Перед ним стояла задача: пополнить археологические фонды музея и создать экспозицию, полностью раскрывающую древнюю историю Хакасии. За 30 лет работы в музее Липский исследовал сотни древних памятников. Среди них известные могильники - «Тас-хазаа», «Федоров улус», «Есинская МТС».

Раскопки Липского дали неизвестные ранее археологические материалы, которые стали основой экспозиции, посвященной древним культурам Среднего Енисея. Также А.Н. Липский изучал петроглифы и собрал большое количество наскальных рисунков. Особое внимание он уделял древне-енисейским изваяниям, что позволило ХКМ к началу 1960-х годов собрать самую большую коллекцию древних изваяний и стел.

Стационарные экспозиции ХКМ на протяжении 1945-60-х годов менялись несколько раз в связи с частыми переездами музея из одного здания в другое. В 1950 году в штате музея числилось 3 научных сотрудника, из них только один имел высшее образование. Но, несмотря на это, экспозиционная работа качественно улучшилась, поскольку комплексная экспедиция музея постоянно пополняла фонды археологическими и этнографическими материалами. В 1950 году ХКМ издал Краеведческий сборник № 1, основанный на материалах археологических исследований А.Н. Липского.

В 1945 году музей посетило 3,2 тыс. человек, в 1955 году - 10,6 тыс. человек, а в 1960 году - 12 тыс. человек.

К 1960 году, как и ранее, отсутствовало приспособленное помещение, не хватало кадров, должного финансирования. По штатному расписанию в музее работало 8 человек, в т. ч. 3 научных сотрудника и директор. Основной фонд музея состоял из 26 тыс. предметов. В 1972 году было принято решение о выделении первого этажа жилого дома по ул. Пушкина, 96 под помещение краеведческого музея. Решение это рассматривалось как вынужденное и временное до строительства отдельного здания музея. В 1978 году облисполком принял решение о строительстве двухэтажной пристройки к краеведческому музею общей площадью 800 кв. м., что позволило музею увеличить экспозиционно-выставочную площадь. Увеличился и численный состав музейных сотрудников - до 35 человек, из них 10 научных сотрудников.

Ведущей формой работы стал оперативный сбор материалов по горячим следам крупных промышленных строек. Шло комплектование материалов по строительству Саяно-Шушенской ГЭС, железнодорожной трассы Абакан - Тайшет, Сорского молибденового комбината. В этот период в музей поступают документы и личные вещи известных людей Хакасии. В результате спасательных археологических исследований в 1970-е годы в фонды музея поступило более двух тысяч археологических предметов. С 1973 года археологом музея стала Э.А. Севастьянова, проводившая охранные раскопки в зоне строительства дорог, Аскизской оросительной системы, Абаканской ТЭЦ, в зоне Подсиненской птицефабрики и в других местах. Неоценимую помощь в копировании наскальных рисунков, попадающих в зону затопления, оказал заслуженный художник России В.Ф. Капелько.

В эти же годы создаются стационарные экспозиции «Хакасия в древности», «Природа Хакасии», «Хакасия в годы Великой Отечественной войны», «Строительство социализма», «Хакасия периода капитализма в России 1861 - 1917 гг.». В 1976 г. за совершенствование экспозиций и работу отдела советского периода Хакасский областной краеведческий музей был награжден Дипломом МК РСФСР, а в 1978 г. - Почетной грамотой Президиума Верховного Совета РСФСР. В 1980 г. открылась стационарная экспозиция «Древнее искусство Хакасии». В 1970-1980-е годы музей организовывал передвижные выставки, что стало новым этапом в развитии выставочной деятельности музея. В 1987 году выставка «Древнее искусство Хакасии с успехом демонстрировалась в Москве и в других городах Советского Союза. В начале 1990-х гг. в ХКМ были оформлены экспозиции «Афганистан болит в душе моей», «Политические репрессии в Хакасии» и «Юрта - традиционное жилище хакасов».

Число посетителей музея с 1960 по 1985 год возросло в 5,5 раза и достигло 105900. Добросовестный труд сотрудников музея был отмечен государственными наградами и званиями. Медалью «За доблестный труд» и медалью ВДНХ была награждена Валентина Николаевна Половникова - директор музея с 1961 по 1990 годы. Звание «Заслуженный работник культуры РСФСР» было присвоено А.Н. Липскому, а звания «Заслуженного работника культуры Хакасии» были удостоены сотрудники музея Л.Г. Угдыжекова и М.Ф. Чалкина.

Постановлением Правительства РХ от 29.09.2006 г. № 256 Хакасскому республиканскому краеведческому музею был придан статус «национального», а 26 октября 2007 года Постановлением Правительства РХ ему было присвоено имя известного исследователя древней истории Хакасии Леонида Романовича Кызласова.

Ранее музей размещался по адресу: ул. Пушкина 96, с октября 2017 музей переехал в Республиканский музейно-культурный центр на ул. Пушкина, 28 А

Площадь Музейно-культурного центра составляет 28 129 кв. метров. По форме здание круглое, вписанное в квадратный участок, диаметр комплекса равен 130 метрам, всего в нем девять модульных блоков: экспозиции, административные помещения, детский музейный центр, фондохранилища. Кроме этого, в здании также будет концертный зал на 600 мест и конференц-зал на 150 мест. Кроме зала каменных изваяний, здесь экспонируются временные выставочные проекты, проводятся массовые мероприятия.