O primeiro Palacio de Capitanía levántase alá polo século XVI no mesmo terreo onde está situado o actual. O paso do tempo deteriora de tal forma o vello edificio de sollados de madeira que o século XVIII ve como acaba definitivamente a súa vida útil.

En 1748, pola Real Orde de Fernando VI reedifícase no mesmo soar un novo edificio, que deberá contar con reloxo, cisterna, cuartos para a vivenda do capitán xeneral e as dependencias do tribunal da Audiencia. Para financiar as obras, acordouse crear un imposto dun maravedí por cada azume de viño que se cultivase en Galicia.

No proxecto inicial, do enxeñeiro militar D. Juan de Vergel, formúlase un edificio de tres plantas, rectangular e cun patio interior. O 6 de novembro de 1748 colócase a primeira pedra do edificio. Vergel falece en 1750 e substituiuno D. Francisco Llovet, que dirixe as obras ata a súa conclusión, e introduce importantes cambios ata o punto que se cre que só respecta as dimensións da planta e do patio interior. A construción do edificio, que conta con dúas entradas para diferenciar claramente as dependencias da Real Audiencia das da Capitanía Xeral, ten unha duración de catro anos, dous máis dos previstos.

As sucesivas intervencións ata o mesmo século XX só afectarán á distribución interior, a cisterna, as canalizacións de pluviais e as naves abovedadas do soto do edificio para arquivo.

En 1910, a planta alta destínase a zonas nobres e vivenda do Capitán xeneral, no lateral esquerdo do edificio constrúense as cortes que se transformarán progresivamente en garaxes e o arquivo, nos sotos do edificio, reconvértese en dormitorios.

Finalmente, en 1996, realízase a última reforma de importancia que lle afecta tanto ao Palacio como á praza da Constitución.