Varios documentos mencionan la existencia de una casa fuerte o fortaleza en la localidad. En 1361 el Conde de Alburquerque entrega el señorío de Villalumbroso a Alfonso Pérez de Bolaños. Posteriormente, su hijo Alvar Alfonso de Bolaños vende en 1374 el lugar con su casa fuerte, sus términos y vasallos, a María de Velasco, viuda de Diego de Sarmiento.
Se menciona la fortaleza sobre 1440 cuando Juan Manrique de Lara y Téllez, conde de Castañeda, ante la infecundidad de su mujer Mencía Enríquez (hija del Almirante de Castilla) busca descendencia en Catalina Enríquez de Ribera, dama de la condesa, quien al enterarse y para alejarla de su marido la casa con el noble Juan de San Pedro. Al conocerlo el conde y para evitar la consumación del matrimonio hace raptar a Catalina y llevarla a su fortaleza de Villalumbroso, donde tuvo sucesor. Años más tarde, tras la muerte de la condesa, para legalizar los hijos tenidos con Catalina Enríquez se casa con ella.
En 1493 el marqués de Aguilar, García Fernández Manrique, por medio de Juan de Bustamante denuncia ante los Reyes Católicos que ha adquirido por compra este lugar y el vecino de Villatoquite, y que su hermano Juan Manrique con gente armada tanto a pie como a caballo ha encastillado sin licencia ambas iglesias y cercado la fortaleza de Villalumbroso. Los reyes comisionan al bachiller Gonzalo de Castro, alcalde de corte, para que se deshagan las obras de fortificación que no existieran previamente.
Vuelve a indicarse la existencia de la fortificación en el testamento de Aldonza Manrique realizado el 22 de enero de 1539 donde entre las propiedades de que disponía en la localidad de Villalumbroso figuran 9 obradas de tierra, la tercera parte de la jurisdicción de los 71 vecinos de la localidad, así como la tercera parte de la fortaleza.
La población es la capital del municipio de Valle del Retortillo, formado en 1973 por la fusión de los de Abastas, Añoza, Villatoquite y el propio Villalumbroso, al que también pertenece el lugar de Abastillas.
Aparece mencionada la localidad en un documento de 1143 del Monasterio de Sahagún con el nombre de "Villa Luminoso".
En 1345 aparece como "Villa Lonbroso" con la iglesia en el obispado de Palencia aunque sin clérigos. Seis años más tarde se encuentra en el obispado de León como lugar solariego de Juan Alfonso que recibe anualmente 3 maravedís en concepto de martiniega por cada suelo. Asimismo le pagan anualmente 400 maravedís en concepto de yantar. Al rey le pagan servicios y monedas, aunque no fonsadera al ser solariegos. Además el merino del rey recibe seis maravedís de entrada.
La población en 1528 cuenta con 112 vecinos pecheros, para en 1591 estar formada por 112 vecinos de los que 106 son pecheros, 2 son hidalgos y 4 pertenecen al clero secular. Ascienden a 123 vecinos en 1631, que corresponden a 428 personas, de las que 321 son mayores de 10 años.
En 1752 la villa es de señorío del Marqués de Aguilar y cuenta con 125 vecinos de todas las clases sociales. Hay en la localidad 102 casas habitables entre las que se incluye la del ayuntamiento y el pósito con capacidad para 200 cargas de trigo, y otras 4 casas en estado ruinoso. Todas las viviendas son de propiedad privada por lo que no pagan por el suelo. Dispone de una casa-mesón que se arrienda anualmente y de taberna, fragua, abacería, carnicería, matadero y panadería.
Con 418 habitantes aparece en el censo de 1768, incluida en la provincia de Toro, corregimiento de Carrión (en la provincia de Palencia) y obispado de León. Pocos años más tarde, en 1787, el número de habitantes asciende a 523, de los que 248 son varones y 275 mujeres. Por actividades hay 59 jornaleros, 39 labradores, 8 artesanos, 6 estudiantes, 6 hidalgos, 3 criados y 1 escribano, además de 8 personas relacionadas con la iglesia.
Existen 5 cofradías en 1771 que celebran 19 fiestas anuales con un gasto que asciende a 20.838 reales de vellón.
Aparece la villa en 1828 incluida en la provincia de Palencia, con 506 habitantes contabilizados como 140 vecinos, que según datos oficiales se reducen a 109 en 1843, de los que 85 son electores, para a mediados del siglo haber 624 almas equivalentes a 120 vecinos, con una población formada por 120 casas Según datos del censo de 1877 tiene una población de derecho de 473 personas, de las que 229 son hombres y 244 mujeres.
Dentro de la localidad la iglesia parroquial está dedicada a San Miguel Arcángel. Es una construcción en piedra y ladrillo del siglo XVII con tres naves en la que la torre se levanta sobre los restos de una previa del XV. En su interior destacar el retablo mayor del XVI. También en el casco urbano se encuentra la Ermita de Nuestra Señora de las Nieves, patrona de la localidad, en cuyo interior se encuentra una talla de la Virgen del siglo XIV.