Queda constancia documental de su existencia en torno a 968, aunque en la zona ya había habido asentamientos anteriores. Su desarrollo e historia están muy vinculados al Camino de Santiago. Su estructura y trazado urbano es el característico del camino que se dirige desde el este al oeste. Existen bastante restos de arte románico siendo citado como uno de los pueblos más importantes del Camino, en el primer Diario de Peregrino, Codex Calixtinus, escrito en el siglo XIII por el clérigo y peregrino francés Aymeric Picaud.
Tiene una dotación de servicios pensados para los peregrinos, dignos de mención. Su albergue es heredero del antiguo Hospital de San Lázaro. Con fecha 15 de marzo de 863, el Cartulario de San Millán de la Cogolla recoge un documento en el que se dice textualmente: "Et septima decanía San Andres de Faiago cum suas uineas et defesas, in montibus et suis pomaribus..." Se trata de la primera referencia a Ayago, como localización geográfica de los Montes de Ayago, con sus dehesas, sus montes y sus manzanos...
En 945 el conde de Castilla, Fernán González concede a San Millán el monasterio de San Martín (entre Redecilla y Grañón).
El año 977 el monasterio de San Millán de la Cogolla devolvió al de San Miguel de Pedroso la villa de Radicella.
A la caída del Antiguo Régimen queda constituida como ayuntamiento constitucional del mismo nombre en el partido de Belorado, región de Castilla la Vieja, contaba entonces con 296 habitantes.
Vías de comunicación en torno al año 1000
Existían bastantes vías de comunicación en las que Redecilla del Camino estaba bien posicionada.
Según el Cartulario de San Milán existía una “ Vía en Estabillo” que se cita en 991. En dicha vía/camino García Pérez y su mujer fundaron una alberguería, que estaba junto al camino de los peregrinos, dándola luego a San Millán y a la que Alfonso VIII concedía exenciones en 1189. Parece que ese albergue estaba situado junto al río Peros, entre Redecilla y Livia (Herramélluri). Anterior a esta vía se cita la de Villazahel a Grañón en 955.
En el año 1025 también el Cartulario de San Millán I nº 179 cita la “strata” (empedrado) de Redecilla a San Martín, primera referencia inequívoca de Redecilla hasta la fecha.
Por otro lado parece que entre Grañón y Oca no había malas condiciones de viaje, pues vemos que el epíteto “vía de carro” se aplica en Grañón en 1032; en 1007 hay una vía de Oca a Cerezo. En 1088 se dice de una vía de Villoria a Beliforamine por citar unos ejemplos (vide San Millán I, núms. 97 y 133 y Valvanera nº 187)
En 1032 encontramos “vía de carro entre” y en 1068 una “vía de mercato” que era distinta de la de Ibrillos.
En fin en 1075 se cita la Vía de Villavenazar a Quintanilla. En 1084 el camino de Francos a Tosantos de 1049 es la primera mención del puente de magazos (vide San Millán I nº 102; Albelda nº21; San Millán núms. 369 y 429; San Millán I, nº 259; San Millán II nº 89).
La conclusión es clara, antes de que decayera el trazado de la calzada romana como oficial camino a Santiago de Compostela que facilitaba el acceso a la Meseta por las proximidades del puerto de la Brújula, ya existían caminos, carreras, stratas y vías que comunicaban la Rioja y la Meseta a través de Grañón, Redecilla, Belorado y Montes de Oca, Atapuerca y Burgos... y que permitieron fijar el camino oficial de los francos al sepulcro de Santiago, por esa zona al sur de aquella calzada por parte de Santo Domingo de la Calzada y San Juan de Ortega, como principales artífices de este cambio.
Santo Domingo de la Calzada (García Domingo nació en Viloria de Rioja el 12 de mayo de 1019, fue hijo de un labrador llamado Ximeno García y de su esposa Orodulce, y falleció en “Burgo de Domingo” con 90 años el año de 1109). Él acondicionó el camino preexistente (una calzada) por la ciudad que llevaría su nombre entre Nájera y Redecilla, trasladando la comunicación que cubría la calzada romana más hacia el sur, por donde transcurre el Camino de Santiago actual. Con ello Domingo García consolida los caminos ya existentes con anterioridad para primar definitivamente el viejo acceso a la meseta a través de los Montes de Oca, como el mejor camino para ir de la Rioja a la cabeza de Castilla. Aymeric ya dice cómo realizó el camino entre Nájera y Redecilla (vide el Codex Calixtinus) por ese trazado, consolidando el tráfico de personas y mercancías por esta reformada calzada.
