Valdeolea es clave para conocer el proceso de romanización de la Cantabria antigua. Su territorio era atravesado por la vía que unía Pisoraca (Herrera de Pisuerga) con Portus Blendium, y sus campos, marcados por numerosos términos augustales (se han localizado casi una veintena) que separaban los prata de la Legio III Macedonica del ager de Julióbriga, el asentamiento romano más importante que hubo en el antiguo territorio cántabro y cuyos restos se alzan en el vecino Campoo de Enmedio. De aquellos tiempos sobresale el yacimiento de Camesa-Rebolledo, sobre el cual se especula pudiera ser Octaviolca. Se trata de una villa con varias dependencias termales, que alojó más tarde una necrópolis y un templo cristiano, ejemplos de la repoblación de la comarca en la Alta Edad Media.
En el siglo X, durante el reinado de Alfonso III de Asturias, Valdeolea y su entorno figuraban integrados en una demarcación territorial denominada Campo Pau. Ya en 1183, en una donación que el rey Alfonso VII de Castilla hizo al obispo de Burgos, la comarca se registra como Campoo y dos siglos más tarde, en el Becerro de Behetrías de 1351, figura dentro de la merindad de Aguilar de Campoo.
Entretanto, los asentamientos permanentes que surgieron en estos siglos en el territorio de Valdeolea se articularon en catorce concejos, institución llamada a pervivir durante todo el Antiguo Régimen: Camesa, con los barrios de Barriopalacio, Camesa y Rebolledo; Castrillo y barrio de La Haya; Cuena y las casas de Monasterio; Espinosa; La Loma; Mata de Hoz; Mataporquera; Matarrepudio; Olea; Reinosilla y venta de Casasola; Santa Olalla; el concejo mayor de Las Quintanillas, compuesto por Bercedo, Las Henestrosas, La Quintana y Las Quintanillas; y las villas de Hoyos y San Martín. Todos ellos dependían del rey, salvo Hoyos y San Martín, que, desde mediados del siglo XV, estuvieron vinculados a la casa Bravo Hoyos. La regulación del funcionamiento de cada concejo se establecía en unas ordenanzas, de las cuales solo se conservan las de Camesa y algunos capítulos de las de Mataporquera. Según las primeras, el concejo estaba administrado por dos regidores y contaba con un fiel, encargado del cobro de repartimientos vecinales.
En los siglos XIV y XV los concejos de los territorios de Campoo se agruparon en las hermandades de Campoo de Enmedio, Campoo de Suso, Campoo de Yuso, Valdeolea, Valdeprado, Los Carabeos y Cinco Villas. Cada una elegía anualmente a un procurador síndico general, vocal nato en las juntas del Ayuntamiento General de la Merindad de Campoo en la villa de Reinosa. Este oficial presidía las Junta de hermandad, compuesta por los regidores y fieles-diputados de los concejos. Todos los años se celebraba una junta (no había fecha fija para la Hermandad de Valdeolea) presidida por el corregidor de Reinosa (cargo creado a finales del siglo XV), en la cual elegían a los procuradores síndicos, a los alcaldes de la Santa Hermandad y, desde 1766, a los diputados de abastos y personeros síndicos del común. Se reunís en Casasola y formaban parte de ella todos los concejos del valle, a excepción de las villas de Hoyos y San Martín y Cuena, que, no obstante, sí pertenecía a la Merindad de Campoo.
Durante el Antiguo Régimen las siete hermandades, la villa de Reinosa y Valderredible formaron parte de la jurisdicción conocida como Corregimiento de Reinosa y Merindad de Campoo (Partido de Reinosa), incluido en el partido de Palencia de la provincia de Toro, circunscripción fiscal surgida en torno al año 1500. Tras la llegada al poder de la dinastía de los Borbones se trató de generalizar y uniformizar la división territorial del Estado, creando intendencias que reunieran las funciones de justicia, policía, finanzas y guerra. Tras varios reajustes quedaron reducidas a 22 en 1749. En las primeras décadas del siglo XIX esta zona conoció diversos cambios: el 24 de agosto de 1803 se suprimió la provincia de Toro y el 1 de enero de 1806 el partido de Reinosa quedó incorporado a la provincia de Palencia. Entre 1810 y 1813 formó parte de la prefectura de Santander; de 1814 a 1822 pasó a la provincia de Palencia; en 1822 quedó incluida en la provincia constitucional de Santander; entre octubre de 1823 y 1833 volvió a formar parte de la provincia de Palencia. Finalmente, en noviembre de 1833 se incorporó definitivamente a la provincia de Santander. Figura como ayuntamiento en el Decreto orgánico de 23 de julio de 1835, dentro del partido judicial de Reinosa.