Conquistado aos Mouros em 1249, pelos cavaleiros da Ordem de Santiago, comandados por D. Paio Peres Correia, o Castelo de Loulé foi integrado na Coroa Portuguesa por D. Afonso III, que lhe concedeu Foral em 1266. O recinto amuralhado englobava a Alcáçova (provavelmente no local onde se instalou a Alcaidaria) e a Medina. A alcaidaria cristã tem possível origem no século XIV, tendo sido remodelada no século XVIII. Recebeu as visitas dos reis D. Pedro I em 1359, D. Afonso V em 1458 e D. Sebastião em 1573.
Após a Restauração da Independência, o castelo perdeu valor defensivo e o crescimento urbano foi englobando os muros. No século XX, desenvolveram-se trabalhos de restauro, com adaptação da antiga Alcaidaria, que atualmente acolhe o Museu Municipal.