En 1861 o arquitecto José María Ortiz y Sánchez redacta o proxecto de construción do edificio. Tras varios anos de cambios e engadidos, as obras rematan en 1880 como indica a placa de mármore situada na fachada principal, aínda que en realidade se seguiron a facer cambios e reformas.

Ademais de cárcere, o edificio acabou sendo un Palacio de Xustiza; no corpo rectangular, con fachada cara á rúa do Príncipe, instaláronse os xulgados e no resto do edificio, o cárcere.

É de planta hexagonal irregular formada por un corpo rectangular con fachada á rúa do Príncipe, un corpo circular no centro do que parten tres naves radiais e por último varios corpos laterais que pechan os lados do inmoble. Este tipo de planta -chamada panóptica- foi deseñada polo filósofo británico Jeremy Bentham (finado en 1832) e utilizada por vez primeira na construción de cárceres no século XIX; con ela conseguíase maior vixilancia, á vez que se creaban varios patios exteriores que facilitaban a ventilación e a entrada de luz natural, ademais de espazos abertos para os presos.

Orixinalmente tiña dúas plantas, mais engadíuselle unha máis nos tres corpos da fachada posterior e a nave central que os comunica. A fachada principal forma un conxunto airoso e harmónico; nela destacamos un corpo central máis saínte có o resto e un zócolo que a percorre lonxitudinalmente. Este corpo é de pedra de cantaría almofadados e presenta unha maior profusión decorativa ca o resto da fachada; del destaca o balcón corrido, situado sobre ménsulas de pedra, e no que se abren tres portas con arcos semicirculares enmarcados en pilastras de estilo corintio e, como remate, un reloxo. A fachada posterior e as laterais son máis pesadas o teñen menos vans.

Os materiais construtivos empregados son o perpiaño de granito e a cachotaría revestida nos entrepanos dos muros.

Este edificio foi declarado Ben de Interese Cultural en 1990.

A remodelación do edificio iniciouse en 1999 e concluíu no ano 2001, para convertelo no museo de arte contemporánea da cidade, actualmente de titularidade municipal.

Da súa remodelación encargouse un equipo vigués de arquitectos formado por Manuel Portolés Sanjuán, Francisco Javier García-Quijada Romero e Salvador Fraga Rivas.

Na reforma mantívose, en todo momento, o esquema orixinal do antigo edificio. Destaca por isto, como sinal de identidade fronte a outros museos, o trazado panóptico das salas de exposición. A súa estrutura está formada por tres galerías e catro patios que parten dun núcleo central, rodeados de salas perimetrais, co que se despraza a entrada das salas de exposición desde a fachada cara ao centro.

No seu exterior construíuse un edificio anexo e un paseo peonil, nas rúas posteriores, que o integran perfectamente no seu contorno.