La fortaleza de Tedeja se localiza al SO del caserío de Trespaderne, en el sector nororiental de la provincia de Burgos, ocupando la cima y la ladera meridional de un anticlinal de la Sierra de Tesla. Este relieve presenta una plataforma superior ligeramente aterrazada en varios niveles, con una marcada pendiente hacia el S que llega hasta la misma margen izquierda del Ebro, donde se abre el “Desfiladero de la Horadada”. Estas condiciones topográficas otorgan a este emplazamiento un indudable carácter estratégico, dotándole de un extraordinario dominio visual. Además, lo pronunciado de sus pendientes, verdaderos cortados rocosos salvo en el flanco N, proporcionan excelentes condiciones de defensa natural, reforzadas por una imponente muralla con cubos hoy visible en el flanco norte pero que al menos por la zona oeste descendió hasta la vega del río, protegiendo el sitio religioso/funerario de Santa María o Santa Olalla de los Reyes Godos, con restos de época tardorromana, visigoda y altomedieval (siglos IV al IX), que está asociado a la zona de habitación.
El castillo de Tedeja aparece citado en las fuentes documentales en numerosas ocasiones, habiendo sido objeto de atención en la historiografía vinculada a la génesis de Castilla como entidad sociopolítica.La procedencia de tales fuentes y referencias son muy variadas, siendo igualmente diversa su fiabilidad, abarcando un lapso entre el 790 hasta 1366.
Las investigaciones arqueológicas dejan constancia de que en realidad el origen de la fortaleza data de siglo V, al final del periodo tardorromano, manteniendo una gran pujanza en la etapa visigoda, seguramente como centro de poder del Alto Ebro. También permiten fijar el final de la fortaleza en el siglo XIV.
Las investigaciones arqueológicas se iniciaron en 1994 y continuaron hasta 1996 de la mano del equipo de José María Ruiz Vélez, Ramón Bohigas y José María Lecanda. Otras campañas se realizaron en relación con la recuperación y consolidación de la muralla, en 2008, con la participación también de María Negredo y Ángel Palomino.