Em meados do século XVIII, época em que foi criada a Capitania de Santa Catarina e nomeado seu primeiro governador, o brigadeiro José da Silva Paes, foi também construído junto à praça da Vila de Desterro um prédio de três seções e dois pavimentos para ser a nova "Casa de Governo".[2] Durante mais de um século, o palácio passou por diversas modificações, até que na mudança republicana uma grande reforma (1894–1898) foi realizada, adquirindo as características arquitetônicas preservadas até o presente.
O palácio foi palco de episódio dramático em função da Revolução Federalista quando, em 1891, foi tomado de assalto por revolucionários que se colocaram contra a política de Floriano Peixoto em Santa Catarina, o vice-presidente em exercício na época.
Em frente ao palácio ocorreu uma grande manifestação contra o regime militar em 1979, que ficou conhecido como Novembrada.
Entre 1894 e 1898, no governo de Hercílio Luz, o prédio foi reformado, perdendo, a partir de então, as características coloniais originais e assumindo linguagem eclética, repleta de elementos decorativos.
Dez estátuas alegóricas esculpidas pelo artista italiano Gabriel Sielva ornamentam a parte externa do prédio, coroando as platibandas. Entre elas, a padroeira do estado, Santa Catarina; a ninfa evocativa dos mares, Anfitrite; e o deus mitológico Mercúrio, compondo com duas barricas, alegoria alusiva ao comércio e à indústria catarinenses, respectivamente, sendo o último localizado no alto da fachada lateral, à direita. Os ladrilhos da calçada à frente do palácio foram importados e assentados no ano de 1910.
O palácio, tombado pelo estado e pelo município, deixou de sediar o gabinete do governador do estado em 1984. O tombamento aconteceu sob o Decreto nº 21.326 de 26 de janeiro de 1984. [1] Foi restaurado em 1977, em 1984 e 2005.[2] Em 1979, passou a ser denominado Palácio Cruz e Sousa, em homenagem ao grande poetacatarinenseCruz e Sousa.[2]
