Fue construido posiblemente por Abderramán en el silgo IX, en el cerro conocido como " Cerro de la Estrella " que presta su nombre a la construcción. Su extensión es de unos 25.000 metros cuadrados, constituyendo una de las mayores fortalezas que se conservan en la provincia de Málaga.
Esta compuesto por dos recintos amurallados, uno exterior adaptado al terreno y constituido por 18 torres más una octogonal, albarrana, y barbacana al noreste.
Con el paso del tiempo ha sufrido varias ampliaciones, siendo zona fronteriza trás la conquista de Sevilla en 1.248, en 1328 paso a manos cristianas despues de su conquista a manos del Rey Alfonso XI, que lo cedió a la Orden de Santiago, y a mediados del siglo XV pasa a monos de Juan Ramírez de Guzmán, a cuyos descendientes se les otorgo el título de Condes de Teba en 1.522.

Destacable en su construcción su planta basilical de tres naves separadas por ocho columnas de mármol rojo de 8 metros de latura y únicas en la zona.

Entre la piezas más importantes que guarda en su Museo-Tesoro, podemos destacar una custodia de plata de 75 cm, de latura, labrada por orfebres cordobeses en el siglo XVII; numerosos cálices, entre los que destaca uno de oro puro de un kilo de peso que data del siglo XV y otro, también riquísimo, con figuras en relieve, donado por el Cardenal Portocarrero y en el que figuran dos inscripciones en latín.

Vista Interior de la Iglesia

Exterior de la Iglesia