Ідея створення нашого музею виникла ще в 1968 році. Саме тоді група експериментального проєктування при кафедрі архітектурного проєктування Київського інженерно-будівельного інституту на чолі з керівником кафедри Миколою Гусєвим розробили виважений ескіз будівлі.
Після затвердження проєкту основні архітектурно-будівельні креслення виконали архітектори М. Гусєв, І. Топор і В. Суслов. Розрахунки конструкцій будівлі здійснив інженер В. Голованевський, а під час будівництва його замінив В. Сідько.
Цікаво, що за планом озеленення навколо музею мали посадити дерева, кущі та квіти, посіяти газонну траву, розмістити доріжки з гранітних плит і поставити садові лавки. А також планували побудувати басейн перед входом. Однак під час погодження і затвердження проєкту, що тривало з 1970 по 1974 р., довелось змінювати багато планів.
У 1975 році розпочалось будівництво музею, яке виконував комбінат Хмельницькпромбуд на чолі з виконробом Ю. Бондарчуком. Не менш важливою була участь будівельних загонів, сформованих із студентів і працівників підприємств Хмельницької області.
Після завершення будівельних робіт у 1978 р. почалось зовнішнє і внутрішнє художнє оформлення, яке здійснювали понад 80 художників-дизайнерів під очільництвом архітекторів і дизайнерів Анатолія Ігнащенка, Анатолія Гайдамаки, Ігоря Скорупського, Леоніда Коваленка та ін.
За спогадами українського архітектора А. Ігнащенка, для зовнішнього оздоблення будівлі мозаїкою було використано близько 25 мільйонів камінчиків смальти. Площа ж навколо музею, яка охоплює понад 10 тисяч кв. м, повністю була мощена гранітною бруківкою.
Оздоблювальні роботи тривали фактично до відкриття музею, яке відбулось 16 червня 1979 р. На церемонії відкриття директору подарували символічний ключ від будівлі, який нині зберігається в нашій експозиції. Завдяки неординарності та монументальності архітектури музей потрапив до каталогів «Музеї світу» (1989 р.) від ЮНЕСКО.
У 2016 році за наказом № 1162 Міністерства культури України будівля нашого музею була внесена до Державного реєстру нерухомих пам'яток України, як пам’ятка архітектури місцевого значення.
