Teba estuvo habitado desde épocas muy antiguas, así queda demostrado en el Museo Arqueológico de la Población (cita obligada para el viajero). Pero fué en la época romana cuando Teba, conocida como Attegua, alcanzó cierto renombre, especialmente como escenario de las luchas civiles entre partidarios de Julio Cesar y los de Pompeyo.
Los romanos construyeron el primer baluarte defensivo en lo que hoy se llma Teba la Vieja y posteriormente los musulmanes reforzaron y ampliaron el cstillo dotándolo de un importante recinto amurallado cuyos restos todavía pueden visitarse. Fue en época árabe, cuando la población, comenzó a trasladarse desde la cumbre del cerro hasta el actual emplazamiento del pueblo que los musulmanes llamaros "Ostipo".

A finales del siglo XIV las tropas de Alfonso XI de Castilla conquistaron la villa y durante los dos siglos siguientes fue cabeza de un importante territorio.

 Uno de los episodios más destacados de la historia de Teba es la muerte de Black Douglas frente a las murallas de su castillo. Este personaje fue un comandante jefe del ejército escocés que, de camino a las Cruzadas y trasportando el corazón del Rey de Escocia Robert The Bruce, se alió con el ejército cristiano que en esos momentos asaltaba el castillo. Hay una placa conmemorativa de aquella batalla en el centro de la población.
Más tarde también los franceses dejarían huella de su paso por la población que durante muchos años fue punto de referencia en la geografía española.