El edificio del Musep Provincia , laCasa de las Veletas  se asienta sobre  un alcázar época musulmana cuyos restos han desaparecido casi por completo, salvo su aljibe, que actualmente se localiza en el subsuelo del palacio. El edificio tuvo una larga historia, siendo destruido varias veces y reconstruido en tiempos de los Reyes Católicos y adquiriendo la apariencia que tiene ahora en 1600. La fachada principal, del siglo XVIII, presenta los escudos de los Quiñones y Cáceres entre los balcones del piso principal.

El origen de la colección que recoge el Museo se remonta a 1899, año en que la Comisión Provincial de Monumentos de Cáceres empezó a recoger antigüedades por toda la provincia, con vistas a la creación de un museo, que se situó en la antigua casa rectoral de los jesuitas, junto a la iglesia de San Francisco Javier. En 1931 se trasladó la colección a la Casa de las Veletas, lugar en el que está en la actualidad, inaugurándose el Museo en 1933.

A partir de ese momento los fondos comienzan a aumentar gracias a donaciones de personalidades locales, por lo cual hay que habilitar nuevas salas de exposición.

En 1972 se remodela de nuevo el edificio, quedando la planta baja y el sótano ocupados por la Sección de Arqueología y la superior por la Sección de Etnografía. Finalmente, a mediados de los años 80 se realizó la disposición de los fondos que ahora podemos contemplar, con algunas modificaciones en los últimos años.