Después de la sucesiva ocupación por parte de Celtas, Romanos y Musulmanes, la ciudad de Campo Maior fue reconquistada en 1230, integrando definitivamente el territorio portugués con el Tratado de Alcañices (1297). El castillo fue construido unos años más tarde, en 1310, por el Rey D. Dinis al mismo tiempo que otorgaba un fuero a la ciudad. Habiendo sido implantado en la cima de la colina de Santa Vitória, a 299 m de altitud, en el centro de la pista, a 10 km de la línea fronteriza y a 18 km de Badajoz y Elvas (lugares que pueden ser vistos desde sus torres).

 A finales del siglo XV, debido a la importancia estratégica de Campo Maior en la defensa fronteriza, el Rey D. Juan II ordenó la construcción de un nuevo conjunto de murallas que albergaría todo el perímetro urbano, que en unos 200 años se había ampliado considerablemente.

Después de la Restauración de la Independencia en 1640, se reforzó todo el sistema defensivo del país, con la construcción de grandes conjuntos fortificados, como Elvas, o la reconstrucción y ampliación de antiguos castillos y fortalezas. En este contexto, en 1645, por orden de D. João IV, se inició la construcción de la fortaleza de Campo Maior, bajo la dirección de João Cosmander, sucedido en este cargo por Nicolau de Langres.

A mediados del siglo XVIII, después de una violenta tormenta y un incendio que dañaron significativamente el castillo, el rey D. João V ordenó su reconstrucción, transformando las antiguas ruinas medievales en una fortaleza más pequeña pero más operativa.  También se construyó la Capilla del Señor de los Afligidos dentro de la valla del castillo en el siglo XVIII