Esta villa posee una venerable antigüedad que alcanza tras el establecimiento defensivo de la línea del Arlanzón, pudieron así los reconquistadores y repobladores cristianos establecer en la margen izquierda del río y colonizar nuevas tierras. Cayuela se pobló al mismo tiempo o muy poco después que Cabia, y de ésta recibió el nombre en diminutivo y se podía leer Cavihuela y otras grafías hasta llegar a la presente.
Esta villa es citada en documentos del siglo IX por vez primera, pero hablaremos de testimonios del siglo XII que no ofrecen grandes cifras de población y de economía, pero poseen un afinado sentimiento artístico, según se puede apreciar en su iglesia de San Esteban. La población de Cayuela no era entonces, y tampoco lo es hoy, muy numerosa; está afirmación del cronista oficial de la provincia, viene a que en los préstamos del obispado de Burgos Cayuela solo aparece con 30 maravedises, mientras que la vecina Cabia aparece con 70, lo cual indica que su población era mucho mayor.
A finales del siglo XVI Cayuela forma partido con otros seis pueblos y entre todos reúnen 184 vecinos, aproximadamente 900 habitantes. Ya en el año 1843 suma 71 habitantes, y en el año 1950, 318. Durante más de mil años de su existencia la villa ha pasado por varias alternativas de administración eclesial y señorial, precisamente depende de la ciudad de Burgos entre los siglos XIV y XVI, al quedar insertada en la jurisdicción de Muñó, volviendo al realengo en el siglo XVIII. Por otro lado, su iglesia parroquial, de estilo románico, muestra su esplendor en su magnífica pila bautismal, que consta de una gran copa piramidal decorada en su interior con gallones y en el exterior con motivos y simbología teológica como monstruos alados, leones, sirenas...