Se aloja en dos edificios históricos del Casco Antiguo de Cáceres, declarado Patrimonio de la Humanidad por la UNESCO. La Casa de Las Veletas alberga las Secciones de Arqueología y Etnografía; se trata de un edificio cuyo aspecto actual tiene su origen en las obras realizadas en 1600 por su propietario Don Lorenzo de Ulloa y Torres en un solar que tal vez pudo haber sido ocupado por el desaparecido Alcázar musulmán. De aquella intervención data el bello patio de planta cuadrada sostenido por ocho columnas toscanas; en el siglo XVIII, sin embargo, la Casa es reformada por Don Jorge de Cáceres y Quiñones, que introduce las gárgolas y los bellos remates de cerámica esmaltada de la cubierta además de los grandes escudos de la fachada principal.
La colección de Bellas Artes se puede contemplar en la Casa de Los Caballos, que fue una caballeriza y posteriormente vivienda hasta su conversión en espacio museístico; objeto de una reciente rehabilitación, fue abierta al público en 1992.
Aunque el primer Patronato del Museo se constituyó en 1917, la idea de su creación surge en 1899 cuando un grupo de estudiosos de la Historia cacereña comienza a recoger objetos de interés arqueológico y artístico depositándolos en el Instituto de Segunda Enseñanza. En 1931 se arrienda el Palacio de Las Veletas para albergar el Museo, que tras una intervención arquitectónica, es inaugurado el 12 de febrero de 1933. Tras la posterior adquisición del inmueble, es rehabilitado en 1971 y se reforma la exposición permanente, tarea que se repite en 1976 en la Sección de Etnografía. En 1989 el Ministerio de Cultura transfiere la gestión del Museo al Gobierno de Extremadura, conservando la titularidad del edificio y de parte de los fondos.