La primera mención a este pueblo del alfoz de Burgos es la recogida en la donación al abad Falconio de Cardeña el 13 de mayo de 994 de ciertos bienes, realizada entre otros por Ermegildo y Gota Lélez de Albiellos.

En su término estaba el monasterio proprio, reliquia namque residentes loci illius Sancti Emiliani, qui est situm in uilla que uocitant Aluiellos, in riuulo Kauie donado primero al obispo de Burgos Gomesano y tras su muerte al monasterio de San Pedro de Cardeña por la religiosa doña Apalla el 1 de octubre de 1045.

En 1066 adquirió el monasterio nuevas heredades en la localidad (in Albillus uilla, in riuulo de Kauie, in alfoz de Uurgos), donadas a su abad Sisebuto por Munio Sonnaz, quien afirma haberlas recibido de su abuela, la antes citada doña Apalla; en 1073 es Rodrigo Sarracínez quien cede sus bienes –kasas et hereditates, solares populatos uel pro populare, exitus et regressus, pratis, pascuis, aquis aquarum uel etiam molinis seu uero uel lignarum arbusculis, uel quantum possum abere in ypsa uilla, cum suis abiacentiis- a Cardeña.

Nada más sabemos de ese monasterio de San Millán, que debió tener vida efímera. El gran monasterio del Arlanzón recibió una nueva donación en Albillos, Villamiel, Villangómez y Bañuelos en 1200 de mano de Ordoño García.

Ya en 1221, doña Mayor cedió a la catedral de Burgos diversas heredades en varios pueblos del entorno de la capital, entre ellas unas sitas en Aluillos et en sus terminos, a cambio de recibir sepultura en la seo.

Al año siguiente, la documentación del Hospital del Rey de Burgos se hace eco de un trueque entre particulares en el que se recogen también propiedades en Albillos.

El pueblo era behetría a mediados del siglo XIV de Pedro Suárez, repostero mayor del rey. De la segunda mitad de dicha centuria debe datar, según Cadiñanos, la maciza torre de planta cuadrada hoy trasladada al hotel Landa, sito en la entrada de Burgos desde Madrid, de la que en 1398 era alcaide Juan Fernández de Riocabia.