Las primeras evidencias de asentamientos humanos en Valderejo se remontan a la Prehistoria (en el Neolítico), como se ha constatado por los hallazgos de campos de túmulos prehistóricos como el de San Lorenzo, lugares de culto y de enterramiento de estas primitivas comunidades pastoriles.
A destacar también las pinturas rupestres de la Edad de Bronce hayadas en un abrigo rocoso en la zona de Portillo Lerón. Son cuatro imágenes que representan un sol, un arquero, una figura antropomorfa y un bóvido.
También se encuentran manifestaciones de la época de la dominación romana, representadas por una calzada romana que discurría (entre Briviesca y Orduña), por el angosto desfiladero de la parte sur del territorio, ya en los límites con la provincia de Burgos.
Pasear por los caminos y sendas que comunican los distintos pueblos y perderse en sus bosques de pinos, hayas y robles, es adentrarse en un entorno natural cada vez más escaso.
Pero la época más importante de la historia de Valderejo, y la que más huella ha dejado, ha sido la Edad Media.
Trás la invasión árabe, Valderejo se hallaba en una situación de "tierra de nadie", abandonada por sus habitantes que se refugiaron en las montañas del norte ante el temor a los musulmanes. Es entonces cuando se produjo un proceso de repoblación del valle llevado a cabo por monjes y abades; los cuales construyeron monasterios, alrededor de los cuales surgen poblaciones.
A lo largo de la historia, este territorio ha estado sometido a diferentes autoridades. El reino Astur, el reino de Navarra, el Señorío de Vizcaya y la Corona de Castilla. Bajo el poder de este último durante muchos siglos.
No obstante, a finales del siglo XII se les concedió un fuero que les eximía de pagar ciertos tributos. Este, fue ratificado por todos los reyes hasta bien entrado el siglo XVIII.
Hasta finales de los sesenta, formaba un municipio cuya capital era Lalastra; pero el abandono posterior de algunas pueblos como Villamardones y Ribera, ocasionó la inclusión de Valderejo en el municipio de Valegovía, al que hoy día pertenece.