A presença humana está assinalada nos territórios de Fronteira desde há mais de 10 mil anos.

Quanto à povoação, a mesma terá sido fundada no reinado de D.Dinis, havendo o registo de que em 1236 a igreja de Fronteira ou Frontaria fica na posse da diocese de Évora. Em carta régia de 1424 Fronteira é agraciada com vários privilégios e em 1512 D. Manuel I dá-lhe foral.

Quanto ao topónimo não há certezas e são apontadas pelo menos três hipóteses. Uma delas invoca a possibilidade de Fronteira ter sido edificada sobre a linha divisória ou fronteira entre os territórios ainda ocupados pelos muçulmanos, a sul, e os recentemente reconquistados pelos cristãos, a norte. Outra versão é a de que a vila foi primeiramente erguida no Outeiro da Vila Velha (e haveria um forte no outeiro de São Miguel) de onde, por razões de salubridade, teria sido transferida para a actual localização no reinado de D.Dinis. Fernando Pina aponta ainda "uma terceira versão, mais erudita, defendida pela investigadora francesa Rosa Plana-Mallart", em que faz recuar a fundação à época romana e o topónimo ao facto de a sua localização se situar no limite - fronteira - da administração dos territoria das civitates romanas de Ebora (Évora) e Ammaia.

Possivelmente nenhuma destas hipóteses estará certa, ou totalmente certa. O castelo, de que há escassos vestígios, marcou uma época e um estatuto para a vila e está ligado intimamente a um episódio maior da história de Portugal e de Fronteira, a Batalha dos Atoleiros.

...Depois de séculos em que integrou apenas as freguesias de Nossa Senhora da Atalaia de Fronteira e de São Saturnino, ao longo do século XIX o concelho de Fronteira contou com múltiplas alterações, integrou freguesias dos concelhos de Estremoz, de Monforte e de Sousel, com significativas mudanças sucessivas e que incluíram ainda a extinção do próprio concelho de Fronteira (em 1867), integrado no de Alter do Chão, mas logo restaurado (1868).

Em 1855 foram extintos os concelhos de Veiros e Sousel, anexando as suas freguesias ao de Fronteira, que desse modo passou a compreender, para além das freguesias de Nossa Senhora da Atalaia e de São Saturnino, as freguesias de São Bento de Ana Loura, Santo Aleixo, São Pedro de Almuro, Rei Salvador, Santo Amaro, Nossa Senhora da Graça de Casa Branca, Nossa Senhora da Graça de Cano, Nossa Senhora da Graça de Sousel e São João da Ribeira.

Em 1863 é restaurado o concelho de Sousel. Depois em 1869 é desanexada a freguesia de São Bento de Ana Loura e em 1871 a de Santo Aleixo, em 1872 foram desanexadas as freguesias de Rei Salvador e São Pedro de Almuro, voltando Fronteira a conter apenas as suas freguesias primitiva de Nossa Senhora da Atalaia e de São Saturnino, acrescidas da de Santo Amaro.
Depois Fronteira vem ainda a receber as freguesias de Vaiamonte e novamente São Pedro de Almuro que voltam a ser desanexada em 1898 para integrar o concelho de Monforte.

Finalmente já em pleno século XX, por decreto de 21 de Dezembro de 1932, Santo Amaro passa a integrar o concelho de Sousel e o de Fronteira integra a freguesia de Nossa Senhora das Candeias, antigo concelho de Cabeço de Vide extinto em 1855 e então integrado no de Alter do Chão.

(fonte: "Fronteira, subsídios para uma monografia", de Fernando Correia Pina, 2001)