De frontera intertribal a mojón fronterizo. En las cercanías dé los baños se alzó el castillo y poblado de Tudején organizado en concejo durante la Edad Media. A menos de cuatro km. un torreón agrupaba alrededor de sí algunos habitáculos en el paraje denominado luego Castellón, actual Fitero. Sobre éste, Avatores y la Morería, culminados por la Peña de Hitero, han conservado asimismo restos de habitación humana muy antigua. Tudejen, Turujen o Turuillen recurren con frecuencia en la documentación navarra. Tras la reconquista definitiva del valle del Ebro por Alfonso el Batallador éste lo cede en su testamento de 1131 a Santiago de Compostela, cesión que no llegó a verificarse por ser impugnado el testamento y advenir García "El Restaurador" al trono navarro. Con la pérdida de la Rioja acaecida durante este reinado, Tudején queda convertido en castillo fronterizo sometido a las violentas luchas entre los reyes de Aragón, Castilla y Navarra. En él se celebraron múltiples entrevistas como la de octubre de 1146 entre Alfonso VII de Castilla y García de Navarra. A esta condición limítrofe aluden los versos populares: Harto era Castillapequeño rincóncuando Amaya era cabezay Fitero mojón.