La etimología de Valdeolmillos proviene del sustantivo latino “Vallis-is” más “ulmus”, olmo, con el diminutivo “-illos” por lo que vendría a significar “el lugar de los pequeños olmos”.
En la documentación del siglo XIV existía el lugar denominado como “Quintaniella de Valde Olmillos”, lugar que se despoblaría en el siglo XVI, ubicado entre Villamediana y Valdeolmillos y que disponía de una iglesia que estaba dedicada a San Millán. En esa misma época también se citaba a “Valdeolmillos” con la iglesia de San Juan que bien pudiera haberse construido en el siglo XI en un estilo románico, del que se guardan restos.
En ese siglo XIV Valdeolmillos era lugar de behetría de Juan Rodríguez de Sandoval, ejerciendo como señores naturales las Lara, Vizcaya y Torquemada.
Ya a mediados del siglo XVIII era villa de señorío perteneciente al Marqués de Revilla, tenía alcalde ordinario y tenia 74 vecinos.
La ermita de la Virgen de del Olmo, adosada al edificio del ayuntamiento, se construyó en el siglo XVI con fuente al lado de esa época.
Conserva Valdeolmillos aún galerías excavadas en las laderas del término que se utilizaban como cuevas para la explotación de champiñón. Cerca del Pico de Solapeña se ha adaptado una de estas “yeseras” en otro tiempo como vivienda rupestre y a la vez de museo etnográfico bien conservado y digno de visitarle.
A mediados del siglo XIX, Valdeolmillos contaba con 505 habitantes, al iniciarse el siglo XX con 431, en 1930 con 415, en 1960 con 301, en 1991 con 88 y en 2006 con 74.