Os vestígios mais antigos da presença do homem no território são achados do Paleolítico. A cultura megalítica e a cultura castreja reflectem-se na sua toponímia. O domínio romano apresenta muitos vestígios na região. Existem lápides epigrafadas e dezassete estações arqueológicas no concelho, na sua maioria restos de villae romanas.

A passagem dos muçulmanos ficou marcada por vestígios ainda existentes na cisterna e nalgumas casas no interior do Castelo.
As primeiras referências escritas datam da época da Reconquista e mostram a importância que tinha para os reis de Leão o repovoamento deste (então seu) território: foi-lhe atribuído o título de vila e foi elevada a concelho por Afonso IX de Leão.

Em 1170 Afonso Henriques conquistou Castelo Rodrigo aos mouros mas ela será novamente perdida, tornando a ser reconquistada por D. Sancho I, em 1209, data em que este lhe concede o seu primeiro Foral.

Castelo Rodrigo, povoação fortificada desde a mais remota antiguidade, foi integrada definitivamente no território português a 12 de Setembro de 1297, pelo tratado de Alcanizes; D. Dinis , que confirma o seu Foral em Trancoso, em 1296, mandou repovoar e reconstruir o Castelo. Sendo palco de constantes guerras, D. Fernando mandou novamente reparar as suas muralhas.

Durante a crise de 1383-85 Castelo Rodrigo tomou o partido de D. Beatriz e de D. João de Castela pelo que D. João I, o Mestre de Aviz, castigou a vila, mandando que o seu brasão ficasse com o escudo das armas reais invertido. De novo a Vila se despovoou e caiu em ruínas.

D. Manuel mandou, novamente, que fosse repovoada, bem como restaurado o Castelo, tendo-lhe dado Foral Novo em 25 de Junho de 1508.

Castelo Rodrigo foi ponto de passagem dos peregrinos que se dirigiam a Santiago de Compostela, aqui acolhidos e cuidados por uma confraria de frades hospitaleiros, estabelecida em Portugal desde 1192.