No se conservan documentos que hablen de una localización exacta, por lo que sus fronteras son difusas y varían según el autor.
Se tiene constancia de la existencia de este territorio gracias a la documentación escrita por el abad Vitulo en un monasterio del Valle de Mena en torno al año 800.
Se le conoce erróneamente como «área Patriniani», debido a una mala traducción del latín.
Tedeja = Tutela, y el antiguo barrio de Trespaderne Paderno = Paternus, situados a la entrada del desfiladero de la Horadada, deben ser considerados como el enclave donde se localizó el castella-castra Paterni, una de las fortalezas erigidas a fines del Imperio romano, y con continuidad en época visigoda, cuya función era el control y vigilancia de los pueblos del norte.
Se cree que este fue el primer castillo de Castilla, pues estudios arqueológicos lo han datado en finales de la época visigoda (siglo V), aunque asentado sobre restos anteriores, posiblemente romanos.