Antes del siglo XIII, en el lugar que ocupa ahora el Santuario, se estableció un monje llamado Guillermo, que emigró a este lugar tras el declive del monasterio de Sahagún.
Éste consiguió congregar a algunos anacoretas e iniciar una vida dedicada a la oración y a la penitencia.
En el siglo XIV los monjes de San Guillermo dejaron estas tierras y el culto a la Virgen de los Valles se abandonó.
En 1470, Don Diego de Prado, hidalgo de la Mata de Monteagudo, encontró milagrosamente una estatua de la Virgen y reanudó así la devoción, dedicándole las obras del Santuario en 1615.
El templo de estilo renacentista contaba con una única nave con crucero y estaba cubierto con bóveda de media naranja. Al fondo se colocó el retablo y el altar de la Virgen y en los lados del crucero, dos retablos que aún se conservan.
A lo largo del tiempo, el Santuario ha sufrido diversas reformas y añadidos como el pórtico en la fachada sur, en la que se abre una hornacina con la estatua de la Virgen Inmaculada sobre la puerta. También se construyeron la torre y el pórtico bajo la supervisión del Maestro Francisco de Mirones y, a su muerte, de Don diego de Falla. El retablo de la capilla mayor se hizo en estilo barroco por los maestros Francisco de Uriarte y Diego de Avendaño. Se realizó también un camarín, en cuyo suelo aparece parte del piso al descubierto enseñando el lugar donde apareció la Virgen, y un coro en el vacío de la torre, además de la Puerta de las Procesiones.
La familia del hidalgo Don Diego de Prado, llamado Don Diego el Dichoso, está enterrada en el Santuario.
En el suelo junto a la pared del norte se encuentran las reliquias de San Guillermo.
Es muy afamada la romería de la Virgen de la Velilla en la pascua de Pentecostés, en la que gentes de toda la montaña acuden al santuario en una celebración muy emotiva y animada.
