De los primeros siglos de la presencia musulmana, que comenzaría allá por el 711, apenas quedan vestigios. Se sabe, por los hallazgos allí encontrados, que se seguiría reutilizando la antigua ciudad romana del Cortijo del Tajo y muchos de los sitios poblados desde aquellos tiempos.

En los primeros momentos la población seguiría siendo mayoritariamente cristiana y posiblemente se sumaría a la famosa rebelión contra los emires de Córdoba que protagonizó Omar Ben Hafsun desde la cercana Bobastro entre finales del Siglo IX y principios del Siglo X. De hecho, los restos constructivos de una torre de vigilancia que podemos observar en lo alto de la Sierra de Peñarrubia  y las primeras estructuras del propio castillo de Teba podrían haber sido utilizados por el poder cordobés para controlar a esta población tan rebelde.

Con el tiempo y con el avance de la islamización de la población, este tipo de conflictos internos se reduciría pese a los constantes cambios de dinastías reinantes: califato, reinos de taifas, almorávides, almohades, nazaríes, etc.

Uno de estos pueblos: el almohade, sería el auténtico artífice de la definitiva construcción del recinto amurallado del castillo, que serviría, entre otras cosas, para la defensa de la numerosa población dispersa por las ricas vegas de los Ríos de la Venta y Guadalteba, plagadas de numerosas alquerías en lugares que nos han dejado abundantes restos materiales y estructuras agrícolas como, por ejemplo, los que encontramos en Nina.

Con el avance de las tropas castellanas, particularmente intenso desde la Batalla de las Navas de Tolosa en 1212, las continuas expediciones de castigo, rapiña y conquista hicieron que Teba fuera un lugar cada vez menos seguro para la población musulmana con lo que el asentamiento en el Castillo, antes sólo ocasional, debió convertirse en permanente. Así estuvo la situación hasta que en agosto de 1330 el rey castellano, Alfonso XI, toma la fortaleza con la anecdótica y singular ayuda de todo un conde escocés; Sir James Douglas, que portaba a tierra santa el corazón del libertador de Escocia; el rey Roberto I.

Desde la conquista castellana hasta  la mitad del siglo XV la villa lleva una vida prácticamente militar sin que los asentamientos de vecinos fueran destacables. De esta época son dos de las principales construcciones del Castillo; por un lado la conocida como Torre del Homenaje y por otro la Iglesia Gótica de lo que hoy tan sólo nos quedan los cimientos.
Sabemos, por los libramientos concedidos por la Corona, que la población habitante del castillo estaría compuesta por un número cercano a las 300 personas, casi todos soldados, y ello debido a la situación de frontera con el reino de Granada que hacía difícil la vida cotidiana por los constantes saqueos de los musulmanes. Así, la zona debió estar bastante despoblada durante este tiempo pese a los distintos privilegios y exenciones de impuestos que los reyes concedían a quien en Teba se instalara.
En 1455 se establece como alcaide del castillo Juan Ramírez de Guzmán. La carrera de este “tebeño” va a ser espectacular puesto que sus continuas batallas contra los musulmanes le harán tomar posesión del señorío de Ardales en 1464, el Rey Enrique IV le nombrará miembro de su consejo real, y llegará a ser mariscal del ejército, ya en tiempos de los Reyes Católicos. Con él tenemos en nuestras tierras al primer representante de los Guzmanes, futuros condes de Teba.