Se trata de un edificio exento que se encuentra en la cuesta que va desde la puerta de Arriaga a la catedral de Santa María. La mayor parte de los muros es de piedra, pero también hay una parte construida con ladrillo y madera y luego enlucida, en la parte superior. Como está construido en pendiente, hay muchas fluctuaciones en la altura de los muros.

Dispone de cubos cilíndricos en las esquinas, del estilo de los torreones que se utilizaban para fortificar las torres durante la Edad Media.

La mayoría de los vanos que se pueden ver actualmente no corresponden a la época de construcción del edificio, lo cual desfigura la estructura original del edificio.

De todas las fachadas, la que da al norte es la que mejor ha conservado la belleza del edificio original. Esa es, en concreto, la fachada de acceso al edificio, a través de un arco apuntado que hay a un lado. También dispone de una pequeña saetera que, según parece, sería el único hueco de la época antigua. La parte superior de esa fachada es saliente y se apoya sobre un sistema de jabalcones. En la fachada derecha, en lugar de jabalcones, dispone de modillones de tres curvas, sobre los que hay un sólido matacán. La galería de la parte superior es muy vistosa; está construida de ladrillo y presenta arcos de medio punto.

A finales del siglo XV y comienzos del XVI, los señores de la época construyeron torres en los puntos estratégicos de las ciudades góticas. La torre de los Anda es una torre-palacio de ese tipo, que actualmente se utiliza como vivienda.