Segundo duas das fascinantes inscrições existentes no castelo, a sua obra iniciou-se em Fevereiro de 1294 e terminou exactamente quatro anos depois; a mesma fonte nos diz que foi seu construtor o mouro Galvo. Porém, ainda em 1280 se fazem referências às relações entre a Ordem de Avis e o Alandroal. No foral Manuelino (1514) refere-se uma primeira carta de foro passada por D. Afonso Henrique, contudo crê-se tratar de um erro e que o primeiro foral seja de 1486, já com D. João II. Era notável a presença da Ordem de Avis no concelho, onde o Mestre tinha uma coudelaria, e a Ordem possuía várias adegas, vinhas, herdades e coutadas.
Por volta de 1384 dá-se uma investida dos partidários de Castela e Pero Rodrigues, alcaide do Alandroal, resiste e sai vitorioso. Não subsistem notícias de conflitos no castelo do Alandroal, somente das investidas a partir do Alandroal de Pero Rodrigues e dos seus homens em defesa das terras vizinhas.
No decorrer das Guerras da Restauração a povoação, apesar de nunca na linha da frente, volta a ter um papel militar quando a fronteira é reforçada com tropas e cavalaria, envolvendo também o Alandroal, como reforço da retaguarda; é então referida a sua importância, sobretudo pelas suas águas, tão necessárias nos verões rigorosos.
O castelo divide-se no castelejo e na alcáçova, e tem uma organização típica de outros castelos de origem árabe. Possui duas torres junto à porta Legal, outra junto à Porta do Arrabalde, a Torre de Menagem, a Torre dos Paços e mais duas distribuídas pelo restante espaço de muralhas. A Cadeia Comarcã é do século XVIII, altura em que é destruída a barbacã e são construídos os Paços do Concelho. Na alcáçova ainda é possível observar o pátio de armas, com a cisterna e as estruturas que quando Duarte d`Armas o desenhou, em 1509, já estava em ruinas. A janela de arco ultrapassado, e a possível torre Albarrã junto á Torre dos Paços, são provas da influência islâmica na sua construção.
Duas personagens naturais do Alandroal são citadas nos Lusíadas: Diogo Lopes de Sequeira, que comandou a primeira frota portuguesa a chegar a Malaca e foi governador da Índia de 1518 a 1522 e Pero Rodrigues, já aqui mencionado - "preso por amigo, preso por leal, Pero Rodrigues é de Landroal".