Historická budova byla postavena v letech 1909-1912 podle plánů význačného českého architekta Jana Kotěry (1871-1923). Projekt vznikal v letech 1905 až 1908 na objednávku muzejního kuratoria (správní výbor muzea) a jeho konečná verze představovala architekturu nejen slavnostně reprezentativní, ale také účelnou, vytvářející i nezbytné podmínky pro provozní potřeby muzea. Architekt Kotěra zde uplatnil asymetrickou dispozici. Půdorys budovy založil na schématu latinského kříže se zkráceným vstupním ramenem doplněným konkávně projektovanou střední částí a rampou, severní křídlo je oproti křídlu jižnímu posunuté směrem k řece a jejich osy se míjí.
V suterénu byly navrženy dílny, místnosti pro technologické sbírky, šatny a umývárny, skladiště, kotelna, byt domovníka, lapidárium a dílenský dvůr. V přízemí byla situována velká čítárna s 62 místy u stolů, knihovna, ředitelna, vestibul, šatna a velký amfiteatrálně upravený přednáškový sál s 200 sedadly, galerií a místností pro přednášejícího. Expoziční sály prvního patra určené pro sbírky uměleckoprůmyslového muzea a druhého patra pro sbírky historického muzea byly zpřístupňovány postupně, jak byl dokončován výstavní mobiliář. V obou patrech byly navrženy ještě místnosti pro kustody a skladiště. Do třetího patra Jan Kotěra umístil fotografický ateliér s horním osvětlením, temnou komoru, několik laboratoří a konzervační sál.
Výstavba jedné z nejkrásnějších královéhradeckých budov probíhala velmi rychle. Na počátku května 1909 byly zahájeny výkopy, 22. srpna 1910 již bylo hotovo třetí patro, práce na kopuli se podařilo ukončit 13. září 1910. Stavba byla provedena v režném zdivu z lisovaných, částečně glazovaných cihel.
Na jaře 1911 byly dokončeny ornamentální a figurální práce z pálené glazované hlíny, včetně dvou alegorických figur sedících žen. Obě byly realizovány podle návrhu Stanislava Suchardy a představují město Hradec Králové v dobách své největší slávy. V roce 1912 budovu doplnily skleněné vitráže ve vestibulech a na schodišti podle návrhu Františka Kysely.
Další úpravy pokračovaly po I. světové válce. V roce 1931 ozdobila kopuli ve druhém patře první mozaika, kterou provedl malíř Josef Novák ve spolupráci se Sklářským ústavem. Zbylé tři byly realizovány až na počátku 40. let 20. století malířem Aloisem Kloudou. Všechny byly zhotoveny podle pastelových kreseb Jana Preislera. V lednu 1934 byl na schodišti do druhého patra instalován světelný stojan, který byl podle návrhu Jana Kotěry zhotoven v dílnách Mistrovské školy zámečnické Státní průmyslové školy v Hradci Králové. Celý projekt byl dokončen v červnu 1934 instalací velké fontány před budovou muzea, která je společným dílem státních průmyslových škol (Státní odborné školy v Supíkovicích, Státní průmyslové školy v Kladně, odborného závodu L. Červinka v Kralupech, Škodových závodů v Hradci Králové). Mistrovská škola zámečnická má hlavní podíl na dokončovacích pracích cizelérských, kovářských a instalačních. Autorem návrhu byl rovněž architekt Jan Kotěra, který navrhl i většinu vnitřního zařízení, včetně čítárny a přednáškového sálu.
Muzejní budova byla v roce 1995 prohlášena národní kulturní památkou a prošla v letech 1999-2002 rozsáhlou vnitřní rekonstrukcí. Další rekonstrukce v letech 2018-2019 se zaměřila především na plášť budovy. Nejvýraznějším zásahem bylo zpřístupnění terasy u kopule na střeše muzea. Nové nátěry oken, očištění cihlového zdiva a vnitřní výmalba sálů a vestibulů měly, podle slov památkářů, vrátit budově vzhled, který ji původně vtiskl architekt Jan Kotěra.
