As primeiras referências ao sítio da Juromenha datam da segunda metade do século IX. Durante mais de duzentos anos este local foi considerado a praça-forte de defesa da zona de Badajoz, pertencendo desde o século X ao Califado de Córdova. Em 1167 D. Afonso Henriques conquistou a fortaleza, mas esta voltaria ao domínio dos mouros em 1191 e só seria definitivamente reconquistada pela Coroa portuguesa em 1242. Mais tarde, em 1312, D. Dinis ordenou a total reconstrução da fortaleza.
No período pós-Restauração, devido à sua importância estratégica, a fortaleza medieval foi adaptada à artilharia seiscentista, tendo sido executadas obras seguindo o plano de autoria do Eng. Nicolau de Langres. A partir de 1662 e durante seis anos, foi ocupada pelas tropas de D. João de Áustria, só regressando à posse da Coroa portuguesa na Paz Geral de 1668.
Com o terramoto de 1755 a fortaleza foi bastante afetada, principalmente a área de edificação seiscentista, tendo sido então reconstruída. Também se construiu um fortim nas muralhas junto ao Guadiana, para aportarem as barcas. No início do século XIX, durante a Guerra Peninsular foi tomada pelo exército de D. Manuel Godoy, sendo só recuperada em 1808. Depois entrou progressivamente em decadência, sendo despovoada em 1920. Mais tarde, a partir 1950 a DGEMN iniciou grandes obras de recuperação que se prolongaram até 1996.
A fortaleza, com planta de modelo poligonal, é constituída por duas cinturas de muralhas, uma interna, onde se situa a torre de menagem, e outra externa, sendo esta de tipo abaluartado, com planta estrelada. No espaço interior da fortaleza foram edificadas as igrejas da Misericórdia e a matriz, e também os antigos Paços do Concelho e respetiva cadeia, e ainda uma cisterna de planta retangular que abastecia a população.
Atualmente, no interior do recinto muralhado existem as ruínas das duas igrejas, da cadeia e dos antigos Paços do Concelho. Em termos paisagísticos, a antiga fortaleza possui uma localização privilegiada, no que respeita ao domínio visual dos territórios português e espanhol.