En el siglo X los árabes fundadores del municipio de Zuheros se sublevan contra el califa Abdelrahman III (primer califa de Córdoba, gobernó al-Ándalus entre los años 912 y 961) construyendo un pequeño castillo roquero que en árabe se denomina Sujayra, nombre del que deriva el nombre de Zuheros.
Abdelrahman III asola la “Subbética cordobesa” metiendo en la obediencia los rebeldes que habían surgido por doquier y construyendo sus castillos. No obstante, Zuheros sigue existiendo. Al destruir sus fortificaciones años después, en mayo del 930 se le llama “lugar de los Banu Himsi”.
Zuheros continuó siendo un distrito de la cora de Elvira (Granada) que existía en el siglo IX. Este distrito o término comunal era un distrito castral formado por complejo alquería y castillo, es decir, un asentamiento campesino y un castillo rural. En este distrito como centro del agrupamiento rural habría una mezquita y un concejo de ancianos.
Zuheros no vuelve a ser nombrado hasta la Primera Crónica general de España de Alfonso X, en la que se habla de la reconstrucción de la fortaleza.
En el 1241 el rey Fernando III conquista Zuheros por pactos y los cristianos se establecen dentro del recinto amurallado de la villa, convirtiendo la mezquita en iglesia parroquial con el nombre de “Santa María” y bajo la advocación de San Matías.
Es en el siglo XVI cuando se edificó el palacio de los señores de Zuheros con un estilo renacentista, cambiando parte de la fisionomía del castillo y de la puerta de entrada.