A sua fundação é antiquíssima, concluindo-se, pelos vestígios existentes, que teve como primeira fortaleza um castro de povoamento, mais tarde transformado num oppidum. A importância da sua situação militar foi sempre grande, desde os tempos da pré-história, visto comandar uma das mais importantes comunicações entre a estremadura espanhola e o Alto Alentejo.

Por esta razão os romanos teriam transformado, segundo a sua técnica castrense, o oppidum lusitano, que devia ser à sua chegada, numa sólida fortaleza.

Foi tomada aos mouros por D. Afonso Henriques, não se sabe em que ano. Este rei mandou logo restaurar o castelo romano e doou a vila ao bravo Gonçalo Mousinho, companheiro de seu pai, o Conde D. Henrique, por se ter destacado nas lutas contra os mouros.

Arruinado o castelo nas lutas contra os leoneses e castelhanos, D. Dinis, em 1299, mandou-o restaurar e ampliar, levantar a torre de menagem e cercar a povoação de uma alterosa muralha, a qual, segundo se crê, só foi terminada no tempo de D. Afonso IV. Deu foral à vila, em 1310, no qual concedia muitos privilégios e isenções aos moradores.

Mais tarde, D. Manuel terá mandado restaurar a fortaleza de Castelo de Vide, muito arruinada palas lutas com os castelhanos, devendo ser essa a representada nos desenhos de Duarte Darmas.