Na colina do castelo ergue-se este monumental Paço dos Alcaides, assim igualmente conhecido, em que a sua edificação teve início nos princípios do século XIV por D. Dinis, sendo João Simão o arquiteto do projeto. Contudo este projeto remonta ao tempo da Reconquista, quando D. Sancho II doa a herdade de Arroiolos ao primeiro Bispo de Évora D. Soeiro, sendo já referida uma autorização régia para a construção de um castelo.
A Reconquista daquela parte do território contribuiu muito para um reverso da fraca densidade populacional existente naquela zona, o que nos finais do século XIII e inícios do XIV viria a justificar o investimento régio do Paço e a fortificação envolvente.
A importância da confirmação de um foral em 1310 também foi a ajuda necessária para a confirmação deste castelo que começara a erguer-se sobre construções existentes com um maior ou menor aproveitamento de um castro proto-histórico, segundo vestígios arqueológicos existentes.
O castelo ergue-se de uma forma curiosa, desenvolvendo-se pelas encostas suaves acompanhando precisamente as curvas do desnível do terreno, podendo assim ter uma melhor visão de toda a vizinhança.
Somente rasgada por duas portas, conhecidas como a Barbacã que se orienta a sul e para o casario que se desenvolveu ultra muras, e a de Santarém que se desenvolve para noroeste, precisamente para a cidade com o mesmo nome. A Barbacã estava ladeada pelas Torres de Menagem e do Relógio.
A Torre de Menagem constitui com o Paço a residência oficial dos Alcaides, destacando-se como anexo principal. De planta quadrada, apresenta ainda vestígios reconhecíveis de que teve quatro pisos de origem, com a parte nobre da casa a compreender o Paço, restando apenas as paredes exteriores rematadas nos ângulos por torres.
A partir do século XIV foi o início do fim do castelo. Durante este século, D. Fernando proibiu os moradores de fora da cerca de ter acesso à igreja que se encontrava no interior. Esta ordem foi uma primeira tentativa para manter o povoamento no interior da cerca, que cada vez mais se tornava impossível, agravando a situação com a ocupação das tropas castelhanas no ano de 1384.
Numa segunda tentativa em 1387, D. João I doou o castelo ao Condestável D. Nuno Álvares Pereira, segundo Conde de Arraiolos, que aqui chegou a habitar e consequentemente fez obras na fortificação e introduziu novas instalações no Paço.
Nos finais do século XVI o castelo ainda era habitado, restando apenas pouco mais tempo, sendo que em 1613 a câmara local já denunciava a ruína do conjunto.
Este panorama viria a degradar-se mais com a chegada das Guerras da Restauração, chegando a resistir a algumas obras feitas por D. João IV. Em meados do séc. XVII a barbacã já estava em ruína, o Paço e a Torre de Menagem também já estavam inabitáveis. Tudo isto veio ainda agravar mais a situação quando aí se sentiu o terramoto de 1755, acrescentando à destruição.
Apesar destas ocorrências de destruição, o castelo em 1910 foi agraciado como Monumento Nacional.
