A vila de Penamacor fica situada a 573 metros de altitude num cabeço fortificado entre as ribeiras de Ceife e de Taliscas.
Tal como qualquer localidade antiga, existem também em Penamacor, lendas sobre a origem do nome. Em Penamacor existem pelo menos três versões diferentes sobre o surgimento da denominação.
A lenda mais antiga conta que Penamacor derivará da junção das palavras "penha" (monte) e "má cor". Segundo a história, o nome de Penamacor deverá ter surgido após uma luta entre o povo que vivia nesse monte e malfeitores, sendo que o sangue derramado das vítimas era de cor negra, de "má cor", ficando assim o monte conhecido como Penha de Má Cor.
Outra lenda conta ainda que o nome desta terra se deverá a um salteador de nome Magor (maior em castelhano), que vivia nesse monte, e a quem se deve a povoação da terra. Isto porque após ter salvado um idoso das mãos de alguns malfeitores, Magor recebeu como recompensa a filha daquele, tendo constituído família. Com os filhos a aumentarem, Magor foi construindo cada vez mais casas no monte onde habitava. Com o passar dos anos, Magor tornou-se apenas uma lenda existindo somente uma povoação que foi crescendo na Penha do Magor, hoje Penamacor.
Mas o mais certo é que a designação de Penamacor seja de origem céltica, derivando de Pen (elevação) e de Magor, passando de "Penha Magor" a Penamacor. Ao que tudo indica, e de acordo com os estudos derivados dos vestígios encontrados na vila, a primeira fortificação terá sido um castro de origem céltica, aproveitado mais tarde pelos romanos.
Mas Penamacor só começa a ter importância quando D. Sancho I a conquista aos mouros, dando-lhe o título de vila em 1199 e o foral em 1209. A construção do castelo e o povoamento da vila de Penamacor devem-se a D. Gualdim Pais, grão-mestre da Ordem dos Templários. D. Gualdim Pais doou terras aos templários, fixando-os assim em Penamacor, atraindo desta forma comerciantes e agricultores.
A vila ganhou importância e cresceu de tal maneira que em 1303 D. Dinis viu-se obrigado a ampliar as muralhas e construir uma nova cintura de protecção.