Valles nació como una ampliación de Palenzuela, población de historia celtíbera y romana. Valles será una de las aldeas de Palenzuela, quedará incluida en su alfoz y participará de la vida entera de la villa matriz y con ella se integrará en la Merindad de Cerrato que bien pudo llamarse de Palenzuela pues de ella era su cabeza. Situada como satélite de Palenzuela, su relación con la administración, política y derecho viaja paralela a esta villa.
Así perteneció al alfoz de Palenzuela como si fuera un barrio de la misma y también a la merindad de Cerrato en el encabezamiento de Palenzuela. Hasta 1833 el régimen local de Valles no cambiará del de Palenzuela. Si ésta está en el realengo, Valles lo estará también; si aquella es transferida al señorío particular como lo será a los almirantes de Castilla o al ducado de Torralba, Valles estará en el señorío. Cuando se organicen Intendencias y su embrión provincial , Palenzuela será asignada a Valladolid y Valles con ella. Valles ha seguido durante el milenio de su existencia todos los lances de la historia castellana, prueba de ello es el fuero que el rey don Sancho otorga a Palenzuela y a sus siete aldeas entre las que se encuentra Valles, Henar y Valparada.
En el fuero se concede a los vecinos de Palenzuela y de sus aldeas algunas exenciones y facilidades: no pagarán portazgos, no aceptarán cargos públicos si no les apetece, se les atenúan las penas en caso de homicidio y prendamiento; los recién venidos, recién casados y viudas no acudirán durante un año a los servicios comunales, no pueden ser mandados fuera de sus términos concejiles y al vecindario, en general, solo se les impone al año cuatro sernas, de un día, para sembar, barbechar, segar y trillar las tierras del rey pero se les servirá pan y vino. Como único impuesto pagarán entre San Miguel (29 de septiembre) y San Martín (11 de noviembre) al fisco el valor de cinco panes y una azumbre de vino, dos denario y una hemina de cebada. Igualmente buena era la real hacienda para Palenzuela y sus aldeas hacia 1350, según se lee en el Libro de las Behetrías. En esta ocasión era la reina doña María, esposa de Alfonso XI y madre del controvertido rey don Pedro, a la que debían pagar 2.400 maravedises por el impuesto de martiniega.
También debían de abonar el yantar (comida) del rey si visitaba Palenzuela. En 1591 Palenzuela y sus aldeas aparecen incluidas en la provincia de Valladolid. En 1833, en la división definitiva de España por provincias, se practica una separación extrema de pueblos en esta parte oriental de Burgos. Palenzuela que era arcedianato de la diócesis de Burgos es adjudicada a Palencia y Valles, su aldea, es incluida en Burgos como ayuntamiento independiente. Tiene entonces unos 356 habitantes, su parroquia sigue siendo de San Esteban y tiene una escuela municipal, pagada con 2.000 reales. En 1900 los habitantes eran 400 y en 1950, 338.
