La presencia del hombre en esta zona se remonta a la Prehistoria, como lo atestiguaan las pinturas rupestres y otros hallazgos de la Cueva de los Murciélagos, que estuvo habitada desde el Paleolítico medio.

Proliferan los yacimientos con restos íberos y romanos. En uno de estos yacimientos con restos, quizás en la romana Sucubo, los musulmanes fundaron hacia fines del siglo IX la enrriscada villa, núcleo y torre vigía, de Suhayra, diminutivo del árabe " sajr", que significa peña. Se dotó más tarde de fuertes defensas, desde el califato al dominio almohade.

Zuheros gozó de una gran importancia militar y estrategia durante la dominación árabe, siendo conquistada tras duro asedio por Fernando III en 1.240, que hubo de tomarla al asalto. De su importancia en la época da idea el hecho de que el rey la cediese a su propia esposa, Doña Juana de Ponthieu.

Como las demás de esta banda morisca por donde corría la frontera con el reino de Granada, se convirtió en una típica villa-fortaleza, marcada por la huella de su pasado andalusí.

En 1.441, Juan II concede el señorío de la villa a Gonzalo Martínez de Córdoba, de la casa de los Aguilar, quién al morir sin sucesión la da a Don Alfonso Fernández de Córdoba, alcaide de los Donceles, en recompensa a sus servicios. Su mecenazgo aportó lustre a Zuheros al construirse un vistoso palacio junto al castillo, a la moda de los grandes nobles del renacimiento. Muerto éste, también sin sucesión, deja heredero a su hermano Don Pedro de Córdoba y Solier, arcediano de Zuheros a favor de su hijo legitimado, Don Alonso Fernández de Córdoba, sobre el que instituyó el mayorazgo.