La localidad de Olmillos aparece ya documentada en el siglo IX, siendo uno de los hitos fundamentales del Camino de Santiago. La familia de los Cartagena se vincula a la villa asegurándose que habían comprado el pueblo a los condes de Castro aunque más bien parece que lo compraron a la orden de Calatrava con la que pleitearon por su posesión. Los Cartagena tuvieron problemas con los vecinos que no los reconocían como sus señores. La familia Cartagena levanta el castillo a la entrada del pueblo, en un altozano, castillo que sirvió de almacén y de punto fundamental a la hora de someter al pueblo a su señorío, pero no fue habitado.
Constaba de dos recintos, del recinto exterior no queda nada aunque tendría tres pequeñas torres en las esquinas y otras dos mayores al Sur, entre las que se encontraba la entrada. Actualmente el castillo está rodeado de una barbacana en ruinas, destacando al Norte dos cubos, mientras al Sur terminan en dos torres cuadradas. En sus lienzos se abren saeteras y troneras.
El castillo propiamente dicho consta de un cuadrado dividido en su centro en dos partes iguales a los que se adosa una torre del homenaje que es la parte mejor conservada.
La flor de lis de los Cartagena aparece en varios cubos de la fortaleza, que posee un matacán sobre la puerta, y en la barbacana un garitón que resguarda la entrada Todavía hoy se puede apreciar que los pisos tuvieron techumbre de madera labrada, y el husillo que comunicaba las plantas.
La parte interior está iluminada por ventanas, algunas geminadas, y otras con asientos labrados en los lados. Una pequeña puerta al norte, junto a la torre, defendida al exterior por ladronera, daba salida a la barbacana.
Bibliografía: VERO DEL, E. (1993): Rutas y Paseos por los Castillos de Burgos. Bilbao.; MORENO GARCÍA, R. (1994): "Inventario de Fortificaciones (Prov. de Burgos)". Castillos de España, $\boldsymbol { \mathrm { n } } ^ { \circ }$ 112. Madrid; MADOZ, P (1984): Diccionario Geográfico-Histórico-Estadístico de España y sus posesiones de Ultramar. Burgos.Ed. facsímil (1845-1850) Madrid. Valladolid. p. 55; CADIÑANOS, I. (1987): Arquitectura fortificada en la provincia de Burgos. Burgos. P. 110