Valderredible y su entorno no estuvo muy romanizada con excepción de las ciudades y villas, y tras la caída del imperio se volvió a formas de vida anteriores. Monjes eremitas se instalaron desde el siglo VI en Valderredible, extendiendo desde aquí el Cristianismo por Cantabria. Valderredible constituyó un importante foco de peregrinaje con su máximo representante en la figura de San Millán. Los primeros evangelizadores se encontraron aún con tribus cántabras reconstituidas después de la pérdida de influencia del imperio romano y que poco después serían incorporadas por Leovigildo al reino visigodo.

Tras la invasión musulmana, en tiempos del reinado de Alfonso I (739-757) se produce un repliegue hasta la franja de la cornisa cantábrica dejando desierta la zona hasta el Duero. Posteriormente se inicia la repoblación foramontana paulatina hacia el sur, donde los repobladores se convierten en pequeños propietarios libres al responsabilizarse del cultivo de las tierras. Valderredible se repoblaría con gentes principalmente de Iguña (valle del Besaya), si bien hubo también movimientos de población mozárabe y algunos pueblos cercanos como Báscones de Ebro, Báscones de Valdivia, etc. fueron repoblados con vascos.

Entre la llegada de refugiados cristianos desde el sur dominado por los musulmanes, y la temprana repoblación iniciada desde finales del siglo VIII y principalmente en los siglos IX y X se llega durante la edad media a la sobrepoblación de Valderredible con sobreexplotación de sus recursos naturales. Se incrementan en esta época las manifestaciones artísticas como la ampliación y mejora de las iglesias rupestres, cerámica, etc.

Los primeros monasterios fundados entre los siglos IX al X fueron transformándose en colegiatas románicas como sucedió con San Martín de Elines. Se configura en Valderredible uno de los grandes focos del románico siendo la colegiata de San Martín de Elines el más claro ejemplo de su esplendor. Valderredible constituye en sus inicios parte integrante del camino de Santiago cuando las tierras al sur eran todavía inseguras.

En los libros “Becerro de las Behetrías (1351)” y en el “Apeo (1404)” se comprueba la evolución desde un régimen señorial dominado por los monasterios de Cervatos y San Martín de Elines, a un dominio compartido con los linajes locales de apellidos como los Calderón, Hoyos, Villalobos, etc.

Por esta época Valderredible pertenecía a la Merindad de Aguilar de Campoo en régimen de behetría donde los propios habitantes tienen derecho a elegir a su señor. Posteriormente pasaría a ser un realengo pasando a depender directamente del rey de Castilla.