Valdujo é indubitavelmente um povoado muito antigo, cuja ocupação ocorreu antes da Nacionalidade.
Sem crer na versão fantasiosa e meramente etnográfica das formigas que fizeram debandar os habitantes da Quinta dos Cordeiros para lugar mais cimeiro, acredita-se que o próprio povoamento de Valdujo terá derivado dos antigos lugares habitados da Volta Larga e da Vila Sousa (Belachousa ou Vila Choisa na deturpação popular). Estas seriam “villas” pré-históricas, como é disso testemunho as sepulturas antropomórficas escavadas na rocha que lá se encontram, bem como os lagares e lagaretas, vestígios que aguardam estudo técnico e apurado.
Esta pequena necrópole da Vila Sousa carece, sem dúvida, de datação cronológica, se bem que, haja a presunção de ser pré-histórica ou mesmo paleocristã. Poderá ser lusitana e escavada em rocha à época do ferro e terá funcionado, como sepulcro ou mortório, até ao advento do cristianismo, aí pelo século II DC.
Da Vila Sousa ou da Volta Larga até aos três povos ou quintãs é uma distância que se calcorreia em meia hora, a passo de marcha. Daí não ser possível assegurar que os habitantes terão procurado outro local para erigirem as suas habitações, pois o termo “andar com a casa às costas”, sabendo que são do granito mais rijo que por aqui se encontra, não tem cabimento.
Do sítio dos Cordeiros, onde a tradição diz ter existido o primitivo Valdujo, atacado por regimento de formigas, que obrigaram os habitantes, numa primeira cautela, a colocarem as crianças penduradas em cestos, também não convence a não ser pelo sentido folclórico. Nem o daquela lenda da moura, filha bastarda do alcaide mouro de Moreira, desalmado pai que a desterrou no Monseco, de onde brota a Fonte da Moura, que sugere a existência de um primitivo povoado entre a Quinta do Cabeço e o Barreiro.
O termo “quintã” com que foram designados os três lugares da povoação é de origem romana (quintana), abrangendo uma ou várias casas e o seu domínio rural.
Com a invasão de um chefe árabe de nome Almansôr, califa de Córdova ou emir de Badajoz, chamado o Açoite de Deus, toda esta região ficou despovoada, pelo menos até à recuperação do território por Fernando Magno, de Leão. Entrou então na posse dos Bragançãos, chefiados por Mendo Alão de Bragança, entrando após nos bens da coroa através da herança de Fernão Mendes, um cunhado de D. Afonso Henriques.
Com a independência de Portugal e ainda no reinado do primeiro monarca português, Valdujo beneficiou do repovoamento comum às terras de Moreira e Trancoso, sofrendo com as guerras posteriores entre sarracenos e cristãos. 
Valdujo pertenceu ao extinto concelho de Moreira de Rei, também designada antigamente por Moreira ou Moreira a par de Trancoso.Isto quer dizer que, desde que Portugal é território independente, até hoje, Valdujo esteve com Moreira 700 anos e com Trancoso os restantes 170. O concelho de Moreira vem desde os primórdios da Nacionalidade (séc. XII) até à saída do decreto de 6 de Novembro de 1836, promulgado pelo governo setembrista de Passos Manuel de Rei foram extintos nessa penada mais 498 pequenos municípios, restando então 351. Foi então Moreira integrada, com as suas freguesias, no concelho de Trancoso.