Hlavním pardubickým ubytovacím zařízením se společenským sálem byla na přelomu 19. a 20. století Veselka. Už v roce 1912 ale začala přemýšlet místní městská a okresní správa o výstavbě nového multifukčního objektu. Pardubičtí měšťané iniciovali první velkou veřejnou architektonickou soutěž, ze které ale nakonec nový hotel nevzešel. K tomu došlo až později, po navázání spolupráce s východočeským rodákem Josefem Gočárem (1880–1945), který roku 1927 vypracoval první návrh objektu. Stavba započala roku 1928, avšak kvůli ekonomickým problémům byl nový hotel dokončen až v roce 1931.
Josef Gočár vytvořil nadčasový palác kombinující umírněné prvky meziválečného funkcionalismu. Po dokončení budovy se ale problémem ukázal být šedomodrý opaxitový obklad. Ten totiž postupně z fasády odpadával, což vtipně glosoval místní humoristický časopis Aprílový marcipán, který napsal: „ouředně bylo zakázáno, aby dlaždičky z fasády padaly.“ Moderní krabicový vzhled stavby kritizovali místní žurnalisté, kteří stavbu označili za sporák.