Existem vestígios da presença humana no concelho, pelo menos desde o período do Paleolítico. Da época dos Romanos subsistem hoje vestígios arqueológicos de uma villa rústica em Santa Vitória do Ameixial e do “Tanque dos Mouros”, estrutura de armazenamento e abastecimento de águas, junto ao lugar das Mártires. Dos povos germânicos, mais precisamente dos Visigodos, existem os vestígios de uma necrópole na Herdade da Silveirona, na freguesia de Santo Estêvão.
Da presença muçulmana, o vestígio mais relevante será um possível arco em ferradura numa das antigas portas da muralha do Castelo de Veiros.
D. Afonso III outorga foral a Estremoz em 1258 e a Evoramonte em 1271. Por sua vez, de Veiros só se conhece o foral de 1510, concedido por D. Manuel I, mas sabe-se que o seu termo já existia em 1258.
Em 1336 a Rainha Santa Isabel morreu em Estremoz, nos seus aposentos situados no Castelo Medieval, sabendo-se que era seu hábito passar longos períodos nesta povoação.
Nas guerras pela independência, ainda no século XIV, Estremoz foi sempre um centro de primeira importância. Serviu várias vezes de local de aquartelamento das tropas fiéis a Nuno Álvares Pereira, que daqui atacavam os invasores castelhanos. Desta terra partiu o Santo Condestável para a famosa Batalha dos Atoleiros.
Já no decorrer da Guerra da Restauração, a Praça de Estremoz foi ampliada e fortemente protegida por um sistema defensivo abaluartado, que abraça o centro histórico num perímetro com mais de cinco quilómetros, cuja maior parte ainda hoje subsiste. Várias batalhas foram combatidas por corpos militares aqui estacionados, como por exemplo a das Linhas de Elvas, a Batalha do Ameixial e a de Montes Claros.
Por sua vez, durante as Guerras Liberais, em Estremoz ocorreu o chamado “Massacre dos Armazéns”, no qual pereceram, assassinados às mãos da população e parte do Exército, mais de 30 presos liberais. A célebre Convenção de Evoramonte foi assinada nesta localidade do concelho de Estremoz, a 26 de maio de 1834, e pôs termo a esta guerra fratricida.
A 25 de Abril de 1974 as tropas do Regimento de Cavalaria 3 saíram de Estremoz em direcção a Lisboa, onde tiveram um papel fundamental para a queda do regime ditatorial.