O Castelo de Castro Marim foi construído num local onde se verificaram ocupações da Idade do Ferro e da época Romana, sendo provável que os muçulmanos tenham fortificado ou modernizado as defesas do antigo castro, que perderam após conquista em 1242 por D. Paio Peres Correia.

O castelo é essencialmente uma fortificação do séc. XIII, a partir da qual se iniciou a reconquista do Algarve aos Mouros. As muralhas, de cor avermelhada e planta semicircular, com uma porta voltada para Oeste e um postigo para Sudoeste, incluem no seu recinto o Castelo Velho, de planta quandragular, com duas entradas e quatro torreões, que terá sido uma construção muçulmana.

Foi a primeira sede da Ordem de Cristo, de 1319, data da sua criação por D. Dinis, a 1334, altura em que transitou para Tomar. Sofreu obras de restauro e ampliação no reinado de D. João IV, época em que, conjuntamente com a Fortaleza de S. Sebastião, se tornou na mais importante praça-forte do Algarve. Sofreu os efeitos do sismo de 1755 que praticamente arrasou a vila.

No interior das muralhas subsistem as ruínas da igreja de Sant'Iago, antiga matriz e do Palácio dos condes de Soure, alcaides da vila. Numa das dependências do castelo está instalado um pequeno museu, com o espólio encontrado.

Sofreu obras de ampliação e restauro iniciadas na época de D. Afonso III e terminadas por D. Dinis. Parece ter recebido reparações na época de D. Manuel, em resposta a queixas dos habitantes de Castro Marim contra a falta de cuidado que os cavaleiros prestavam às instalações militares, como o testemunha o Livro das Fortalezas de Duarte de Armas cujos desenhos apresentam um castelo já em excelente estado de conservação. Depois de 1640, D. João IV mandou-o reparar e aumentar, tendo a sua capacidade defensiva sido completada com a construção do Forte de S. Sebastião, no cabeço fronteiro ao castelo.