Su historia puede remontarse al Paleolítico Superior, manteniendo grabados rupestres con la "Taja de los Hierros", y abundantes piedras y hachas pulimentadas que así lo testifican. No obstante, la primera población estable se dio en la Mesa del Esparragal, donde se halló el "Bronce de Lascuta" (189 a. de Cristo), primera inscripción romana de España, conservada hoy en el Museo del Louvre. Con los visigodos, la localidad adquirió nuevo carácter y de esta época datan tanto la actual torre de la Mesa del Esparragal como la desaparecida Ermita de los Santos Nuevos, donde se encontraron reliquias de los Santos Mártires Servando, Germán, Saturnino, Justa y Rufina así como del precursor San Juan, que se guardan actualmente -junto a la lápida que los identifica- en la Parroquia de San Jorge.

Tras la conquista musulmana la población pasaría a llamarse "Qalat at Yazula", o "Castillo de los Gazules", al ser entregada por el rey de Granada a la familia o tribu del mismo nombre. Durante los períodos emiral y califal estuvo incluida en la cora de Algeciras, de ésta época aún se conservan los restos del Castillo.

En 1264 la ciudad es reconquistada por la huestes cristianas de Alfonso X el Sabio, quien en su "Crónica" es el primero que le da el nombre de "Alcalá de los Gazules", años más tarde pasaría a depender del Señorío de los Ribera, Duques de Alcalá, quienes ejercieron el patronato secular construyendo iglesias y conventos como la Parroquia de San Jorge, Santo Domingo, San Francisco (La Victoria), Las Clarisas...
La época contemporánea se abre para Alcalá con la presencia de los franceses, quienes a su marcha volaron el hasta entonces intacto Castillo. En Junio de 1876, Alfonso XII le concede el título de Ciudad en consideración a su progreso en población, comercio e industria.

En 1985 se declaró el vericueto de calles de su casco antiguo "Conjunto Histórico-Artístico", tanto por atesorar un importante conjunto de extraordinarios ejemplos de edificios barrocos, neoclásicos, eclécticos y de arquitectura popular como porque ha sabido conservar su estampa y fisonomía andaluza.