Antecedentes
A primitiva ocupação humana do seu sítio perde-se na pré-história. Acredita-se que foi habitada sucessivamente por povos Celtas, Romanos e Muçulmanos, para ser reconquistada por forças cristãs do reino de Leão no século XIII, após 1230. O primeiro foral de Campo Maior data de 1260, outorgado pelo Bispo de Badajoz.

O castelo medieval
A vila foi conquistada por forças portuguesas entre 1295 e 1296. Só seria, entretanto, incorporada definitivamente aos domínios de D. Dinis (1279-1325) em virtude do Tratado de Alcanises (1297). Para incrementar o seu povoamento e assegurar-lhe a defesa, o soberano concedeu-lhe Carta de Foral e determinou a reconstrução do seu castelo (1310). Diante do crescimento da povoação e da sua importância estratégica sobre a raia alentejana, D. João II (1481-1495) ampliou-lhe as defesas, fazendo erguer uma nova cerca envolvente que inscrevia toda a vila dentro das muralhas. Esses trabalhos prosseguiam sob o reinado de D. Manuel I (1495-1521), quando foi figurada por Duarte de Armas no seu Livro das Fortalezas.

Da Guerra da Restauração aos nossos dias
Nos séculos XVII e XVIII, diante da modernização dos meios ofensivos, a defesa da vila foi remodelada com a introdução de linhas abaluartadas e construção de novas instalações militares, transformando a povoação medieval em uma Praça-forte.
O conjunto medieval foi severamente danificado em 16 de Setembro de 1732. Por volta das três horas da madrugada, durante uma violenta tempestade, registou-se a queda de um raio sobre a torre grande do castelo, utilizada como paiol de pólvora. O paiol estocava, naquele momento, seis mil arrobas de pólvora e cinco mil munições. À violenta explosão seguiu-se um vasto incêndio, que além das vítimas fatais, consumiu mais da metade das habitações da vila, arrasando não só o castelo como a cerca medieval. No século XX o castelo foi classificado como Monumento Nacional por Decreto publicado em 18 de Março de 1911. Na primeira metade da década de 1940 a Direcção-Geral dos Edifícios e Monumentos Nacionais (DGEMN) iniciou obras de consolidação e restauro do conjunto, caracterizadas por trabalhos de reconstrução. Uma segunda etapa de obras foi iniciada na segunda metade da década de 1960, estendendo-se até ao início da década de 1970, marcada por intervenções nas muralhas do castelo e na Capela de Nossa Senhora dos Aflitos. Uma terceira etapa teve lugar na década de 1980, passando o monumento para a afetação do Instituto Português do Património Arquitectónico (IPPAR) a partir de 1996. No início de 2010 registou-se o desmoronamento parcial do monumento devido ao mau tempo ocorrido na região.