A fortaleza de Tebra foi construída por Pedro Álvarez de Soutomaior (o “Madruga”), conde de Caminha, en 1478, tendo sido demolida pouco tempo despois (1482). Supostamente no mesmo lugar foi erguida, por volta de 1533-1534, unha nova Torre por Álvaro Suárez de Deza.
Esta nova Torre presentaba outros elementos unidos, e rodeándoa, unha serie de construcións de épocas distintas, que compuñan un pazo señorial. Apesar da adición de parapetos e ameas, levadas a cabo nos edificios residenciais, o conxunto, dominado pola Torre, non parece ter calquera función defensiva.
A Torre é cadrada, de 8,50m de lado, cunha espesura de muros de cerca de 1,40m. Para realzar a súa silueta a Torre foi coroada cun parapeto con ameas, lixeiramente saliente e sustentado por soportes, con catro garitas circulares nos ángulos, sustentadas por unha base tronco-cónica invertida.
Toda a Torre, coa súa aparencia actual carece de valor defensivo, como foi xa referido, obedecendo máis a unha arquitectura teatral que propiamente militar. O seu principal obxectivo é garantir un efecto escénico con referencia a un dominio señorial sobre o territorio situado ao redor.