A origem deste castelo beirão não é determinada, sendo, provavelmente, um antigo castro lusitano que, posteriormente, seria ocupado pelos romanos. Uma vaga diversificada de povos invasores cobiçaram e conquistaram esta fortaleza. Os árabes foram os seus últimos ocupantes, expulsos em definitivo por D. Afonso Henriques no século XII.
Vários episódios marcaram este castelo durante a Idade Média, nomeadamente quando existiram disputas entre portugueses e castelhanos, ou ainda mesmo quando crises de poder marcaram a monarquia portuguesa. Nos diversos episódios em que o Castelo de Celorico da Beira foi protagonista, os seus defensores revelaram-se sempre corajosos e leais ao nome de Portugal, traduzindo essas qualidades nas simbólicas armas heráldicas da vila.
O actual traçado do Castelo de Celorico da Beira define-se nos reinados de D. Afonso Henriques e de D. Sancho I, numa época em que a área geográfica da Beira - a linha formada pelos castelos de Trancoso, Celorico e Linhares da Beira - estabelecia a fronteira entre o norte cristão e o sul muçulmano. Com D. Dinis, D. Fernando I e, posteriormente, D. Manuel I, foram empreendidas novas campanhas de melhoramentos da fortaleza.
A planta do castelo medieval desenha uma oval irregular, interrompida por dois quadrados de desigual dimensão e um rectângulo de maiores proporções. Situa-se numa colina rochosa e escarpada, à altura de 550 metros, o que facilitava a sua defesa e dificultava a progressão dos invasores.
Delimitam-no espessos e bem aparelhados panos de muralha, reforçados nos ângulos do lado Nordeste por dois cubelos assimétricos e quadrangulares. Corre no topo desses panos um adarve comprido e largo, também denominado por caminho de ronda. A ele se ascende por escadas estreitas e íngremes de alvenaria. Remata esta estrutura um parapeito contínuo - que terá sido rematado por ameias quadradas que desapareceram.
Integrado ainda na muralha, embora se destaque com nitidez, localiza-se a Sudeste uma grande torre quadrangular ameada, com porta rectangular e frestas, sendo o seu acesso estabelecido por estreitas escadas de pedra. Poderá corresponder à Torre de Menagem da fortaleza, embora existisse no centro do pátio uma outra torre, igualmente elevada e quadrangular, que foi demolida por se encontrar quase totalmente desmantelada no século XIX. Esta situava-se por cima da cisterna do castelo.
Rasgam-se nas paredes exteriores do castelo duas portas: a porta da traição, localizada na íngreme face Ocidental da colina, e a porta principal, virada a sul. Próximo da entrada nobre, anexa às muralhas do castelo, principiava a cerca da vila. Quase totalmente desaparecida em meados do século XVIII, a cerca da vila resguardava a zona íngreme de ruas estreitas e tortuosas da antiga povoação de Celorico da Beira que cresceu à sombra protectora do castelo. Como vestígio material desse sistema defensivo apenas subsiste a Torre do Relógio.