Nos tempos em que existia em Proença-a-Nova grande quantidade de cortiça, um grupo de habitantes decidiu fazer uma torre que os levasse até à lua. Começaram a reunir e a empilhar cortiços sobre cortiços, subindo cada vez em direção à meta. Quando já muito tinham trabalhado e estavam quase a atingir o objetivo, faltando colocar apenas um último pedaço, aperceberam-se que tinham esgotado toda a cortiça disponível e mesmo depois de percorrerem o concelho não conseguiram encontrar mais.
Depois de muito pensar, um deles pensou ter encontrado a solução:
- Já sei! Tiramos o cortiço do fundo e colocamo-lo em cima, a terminar a torre.
Assim fizeram e claro que a torre de imediato se desmoronou.
Uma segunda parte da lenda retrata uma certa rivalidade que sempre existiu entre Proença e Sobreira Formosa, que chegou a ser sede de concelho. Ao ver a queda da torre, um dos que estava no cimo da pilha gritou de imediato:
- Eh rapazes, aí vai a cortiçada a caminho da Sobreira!
Ficaram então os habitantes de Proença-a-Nova conhecidos como Cortiçolas e os da Sobreira como Cascorros (designação dada à pior parte da cortiça). Durante muito tempo Proença-a-Nova foi conhecida como Cortiçada.
Diz a lenda que os mouros, quando foram expulsos da região, se esconderam nos buracos escavados nos penhascos que ladeiam a aldeia de Chão do Galego. Assim teriam sobrevivido por muito tempo, sendo a última habitante da gruta uma moura que todas as manhãs se penteava à entrada. Era lá que os pastores a viam e conversavam com ela.
- Olhem lá, qual é o mais bonito, o meu ouro ou o meu cabelo?, costumava perguntar-lhes.
Se eles respondiam que era o ouro, ficava zangada e não lhes dava nada. Mas se lhe elogiavam o cabelo recebiam uma caixinha com carvões e, no dia seguinte, em vez de carvão encontravam bocadinhos de ouro. Por baixo da “Buraca da Moura” haveria, segundo a lenda, um corredor subterrâneo através do qual ela iria buscar água ao pego do Almourão.
A tradição atribui o nome a um episódio perdido no tempo, num dia em que três raparigas bonitas estariam a fiar e conversar à sombra de um sobreiro, quando por ali passou um visitante. Apontando uma delas, o desconhecido terá repetidas vezes admirado a sua beleza, dizendo o quanto era formosa. O caso tornou-se conhecido e fez eco das palavras sobreira e formosa, originando o nome com que a terra foi batizada.
Outra versão conta que o nome da freguesia provém de uma sobreira que sobressaía entre todas as outras que existiam em grande número na região. Mais frondosa e formosa que as restantes, a referida árvore, no local do atual adro da igreja, servia de abrigo aos visitantes que sob os seus ramos descansavam e se protegiam da chuva e do sol. À sua volta foram sendo construídas as casas que, com o passar dos tempos, originaram a povoação.
Conta-se que um rapaz do Espinho ia à escola a Proença e descia a pé o Vale Fagundes, naquele tempo muito temido por causa dos “medos”. Como a distância até à escola era muita, o garoto passava no local de madrugada e, ao final do dia, já noite cerrada. A maior parte dos dias chorava com medo e queria desistir de ir à escola.
Uma noite, apareceu-lhe uma senhora vestida de branco, que o aconselhou a ter coragem e a ser persistente no estudo, porque um dia haveria de ser padre. Daí para diante, o rapaz não voltou a ter medo nem desistiu de ir à escola, prometendo que se um dia fosse mesmo padre construiria no local um arco de pedra, para recordar aquela aparição.
Assim teria nascido o Arco da Moita, que ao longo dos tempos foi assinalando o cruzamento da estrada principal com a via que conduz ao Vale das Balsas. Depois de ter sofrido alterações de localização, o arco foi recentemente removido devido às obras de construção do IC8, voltando ao que seria o seu local de origem.
Durante a primeira Invasão Francesa, um batalhão comandado pelo cruel Loison, permaneceu 37 dias em Proença-a-Nova. Os soldados franceses teriam conseguido apanhar a pesada cruz de prata que contém a relíquia do Santo Lenho, oferecida à vila pelo filósofo quinhentista Pedro da Fonseca. Milagrosamente, a prata ter-se-á transformado em lata e os soldados deixaram-na para trás, por julgarem que não tinha valor.