El casco urbano de Mucientes está ubicado sobre la ladera meridional de una lengua desgajada del páramo de Torozos, enmarcada entre los valles que han formado los arroyos del Prado -principal arteria fluvial de Mucientes, que discurre en dirección oeste-este y, ya en el término de Cigales, desagua en el Pisuerga- y un afluente de aquel, el arroyo de los Pradillos, que desciende del páramo y está situado a unos $5 0 0 \mathrm { m }$ . en dirección oriental.
Tenemos abundantes datos acerca de la historia de Mucientes en época medieval. A partir de 1114, el conde Pero Ansúrez dona la iglesia de Mucientes a Santa María de Valladolid (Mañueco y Zurita, 1917-1920 [I]: 97) y posteriormente, en 1117, a San Isidoro de Dueñas (Reglero de la Fuente, 1994: 89). En aquel entonces, jugó este municipio un papel destacado dentro de la red de comunicaciones, pues se ubicaba junto al camino que atraviesa el Páramo. Además se disponía en una situación estratégica en la ruta alternativa a la que pasaba por Cabezón, a medio camino entre Dueñas y Valladolid y por su proximidad a la frontera palentina. También fue un centro destacado en lo que al poblamiento se refiere, en la red de hábitat de principios de siglo XIII, aunque a mediados del siglo XIV queda ya relegado a un segundo plano, pese a que cualitativamente sigue teniendo importancia en la organización del poblamiento de la comarca de Torozos (Reglero de la Fuente, 1994: 104, 105 y 141).
El Palacio, estratégicamente emplazado en la parte más elevada del casco urbano, aparece citado por primera vez en el año 1326, en el Archivo Ducal de la Casa de Medinacelli en Sevilla. Posteriormente, en 1410, es mencionado como "casa fortaleza" en el trueque en el que el convento cisterciense de San Felices de Amaya otorga el lugar de Mucientes, su casa fuerte, señorío y jurisdicción, y demás casas y propiedades del monasterio a García Fernández Sarmiento, Adelantado Mayor del reino de Galicia, a cambio de bienes y rentas que el Adelantado tenía en Melgar de Fernamental, Padiella de Yuso y Zorita. Y, en la Crónica de Juan II, año 1432, como "castillo" en el que dicho rey tuvo en prisión a Don Diego de Sarmiento, Adelantado de Galicia. También en esta villa y por orden suya, Don Diego de León hizo frente al rey de Navarra y al infante Don Enrique (Ortega Rubio, 1979 [II]: 199).
En 1470 se sabe en propiedad de los Zúñiga, pasando a formar parte de la familia de los Sarmiento-Mendoza en 1530. Durante estos siglos -XV y XVI- se halla al frente del mismo un "Alcaide", que hacia mediados del siglo XVI se convierte en "Alcaide Mayor".
A comienzos del XVI, estuvo en Mucientes la reina Doña Juana la Loca a su regreso de Flandes, en compañía del Cardenal Cisneros y de Garcilaso (Ortega Rubio, 1979 [II]: 200). Doña Juana reposó en la fortaleza que era ya propiedad de los Ribadavia (Urrea, 1974: 101).
Especial relevancia cobran las referencias contenidas en el Catastro de Ensenada de 1751, que hace alusión a él como castillo arruinado, propiedad del Conde de Ribadavia. En efecto, es en este documento donde se proporcionan las medidas del Palacio: 66 varas de frente y 220 varas de fondo (una vara equivale a $0 { , } 8 \mathrm { m } .$ .).
En 1823 comienza su demolición. A partir de entonces se permite en varias ocasiones sacar piedra del mismo, sirviendo así como cantera. En 1893, Ortega Rubio (1979 [II]: 201) lo visita y dice que solo se conserva un lienzo de muralla.
Hoy día, de El Palacio solo se conserva algún relleno de muro, a partir de los cuales es imposible reconstruir la fisonomía original del edificio. En la década de los años 80, la Asociación Cultural Albillo de Mucientes intenta llevar a cabo una intervención arqueológica en el Palacio; sin embargo, no se le concede el oportuno permiso para su excavación. Carlos Duque ensaya una reconstrucción del Palacio: defendido por dos lienzos de muralla apreciables en los fotogramas, incluiría en su interior una edificación defensiva y, al mismo tiempo, palaciega, como demuestra la existencia de la Torre del Homenaje con ventanales decorativos; inmediatamente al norte de la torre aún se reconoce un foso excavado en la zona más accesible al castillo, que separa la torre y los lienzos de muralla que la ciñen por ese sector -de los cuales solo queda hoy el relleno de los muros- del terreno circundante; además, con muchas dudas, en una de las fotografías citadas, al sur de la torre, en el lienzo de muro más interior, parece apreciarse un bastión triangular o una estructura similar.
Un escudo que en su día debió pertenecer a los Ribadavia (Urrea, 1974: 99) se halla hoy insertado en la pared de una nave agrícola que se encuentra al sur de la carretera que desde Mucientes conduce a Cigales. En él están representados trece roeles y dos cráteras con motivos vegetales.
Además de los elementos arquitectónicos relacionados, cabe hacer referencia a ciertos informes orales (Lorenzo Sarabia y otros lugareños) que testimonian la existencia de una estructura subterránea consistente en un "sótano" con muros hechos con piedra sillar y cubierta abovedada con arco. Los mismos vecinos, que aseguran haber estado hace ya tiempo en ese sótano, recuerdan asimismo que sacaron de allí "azulejos".