Se trata de un edificio singular dentro del panorama de la ciudad monumental cacereña, pues está levantado sin elementos defensivos en la mayor parte del solar del antiguo alcázaralmohade. En esa área Diego Gómez de Torres levantó un edificio a partir de 1477, pero el edificio actual se debe a Lorenzo de Ulloa, que lo reformó completamente hacia 1600. Sobre la portada principal destacan dos grandes escudos barrocos con coronas voladas y referencias a linajes cacereños, como los de los Torres y los Ulloa. Una balaustrada con gárgolas y pináculos de cerámica remata el edificio, en la cual se encontraban las veletas que bautizaron al edificio.
El museo alberga colecciones importantes de arqueología, etnografía y bellas artes. Pero, sin duda, lo más destacable del mismo es el aljibe, excavado en parte en la roca natural. De planta irregular, tiene aproximadamente 15 metros de largo por 10 de ancho. 16 arcos de herradura sustentados por 12 columnas, algunas de origen romano, forman las cinco naves de bóveda de que consta la construcción. Aunque se hayan barajado las hipótesis de su utilidad como baño o mazmorra, su finalidad última era la de almacén de agua de la lluvia. Puede considerarse el más importante y mejor conservado de la península ibérica tanto por sus dimensiones y estructura, seguido por el de Constantinopla.
La estatua del Genio Andrógino, célebre figura en la ciudad, se encuentra en la entrada del museo.