En época musulmana, la población se asentó en el cerro donde se edifica el castillo, dando el nombre de Hisn Al-Qabdaq -ciudad de los manantiales. Se elige esta ubicación con motivos militares para defender la posición y estar en contacto con el Castillo de Martos y la Fortaleza de la Mota de Alcalá la Real a través de sus atalayas dispuestas estratégicamente a lo largo del territorio.
En sus primeros años el Castillo sirvió para combatir las luchas internas del Califato de Córdoba y no es hasta la época de Abderamán III cuando la fortaleza esté controlada. Los almohades en el siglo XII ampliaron y fortificaron las antiguas defensas emirales. Alcaudete se había convertido para este tiempo en una próspera medina surgida en torno a su castillo.
En el año 1246 sucede la primera conquista de la fortaleza del rey Fernando III, quien la entregará a la Orden de Calatrava y a su maestre, Don Fernando Ordóñez. Serán los calatravos quienes, en la segunda mitad del siglo XIII, edifiquen la fortaleza que hoy podemos contemplar sobre la antigua de época musulmana.
Al estar tan cerca de la frontera con Granada, es un lugar de batalla, conquistando de nuevo en el año 1300 el sultan Muhammed II al-Faqih.
Finalmente, en 1312 al mando del infante Don Pedro, hermano del rey Fernando IV, conquistó definitivamente el castillo de Alcaudete. Comienzan uno años de esplendor, concediendo a la villa privilegios del Fuero de Córdoba. En 1408, Muhammad VII lanza un último asedio, logrando conquistar la población pero no el castillo, que resiste hasta que el 18 de Febrero el sultán se rinde y se retira.
A partir de entonces, Alcaudete y otros pueblos fronterizos se convierten en lugar de entrada de las tropas castellanas en territorio nazarí. Queda anotada la presencia de los Reyes Católicos por estas tierras en torno al año 1490, cuando pasan y se detienen en Alcaudete en varias ocasiones. Tras estos años, el Castillo pasa a titularidad de los Condes de Alcaudete, que edifican el castillo sin modificar las estructuras originales, pero lo abandonan debido al terremoto de Lisboa en 1.755 que causa daños. Pasa a manos del Ayuntamiento debido a las desamortizaciones del siglo XIX.
El Castillo de Alcaudete es declarado Bien de Interés Cultural en 1985.
