Depois de ocupação sucessiva por Celtas, Romanos e Muçulmanos, a vila de Campo Maior foi reconquistada no ano de 1230, integrando definitivamente o território português com o Tratado de Alcanices (1297).  O castelo foi mandado construir alguns anos mais tarde, em 1310, pelo rei D. Dinis ao mesmo tempo que concedeu carta de foral à povoação. Tendo sido implantado no topo do Outeiro de Santa Vitória, a 299 m de altitude, em plena raia, a 10 km da linha de fronteira e a 18 km de Badajoz e de Elvas (lugares que se avistam das suas torres).

Nos finais do século XV, pela importância estratégica de Campo Maior na defesa fronteiriça, D. João II mandou edificar um novo conjunto de muralhas que albergasse todo o perímetro urbano, que, em cerca de 200 anos, se expandira consideravelmente.

Depois da Restauração da Independência, em 1640, todo o sistema defensivo do país foi reforçado, com a construção de grandes conjuntos fortificados, como Elvas, ou a reconstrução e ampliação de antigos castelos e fortalezas. Nesse contexto, em 1645, por ordem de D. João IV, iniciaram-se os trabalhos de construção da fortaleza abaluartada do Castelo de Campo Maior, sob orientações de João Cosmander, sucedido neste cargo por Nicolau de Langres.

Em meados do século XVIII, depois de uma violenta tempestade e um incêndio danificarem significativamente o castelo, D. João V ordenou a sua reconstrução, transformando as antigas ruínas medievais numa fortaleza mais pequena, mas de maior operacionalidade.  No interior da cerca do castelo foi ainda edificada, no século XVIII, a Capela do Senhor dos Aflitos.