En 1867, en las excavaciones llevadas a cabo por Don Luis Maraver y Alfaro, aparecieron más de doscientas sepulturas, cerámicas y objetos diversos. Con posterioridad, Pierre Paris y Arthur Engel hallaron restos prehistóricos, fenicios y griegos. El poblado prehistórico se asentó en el lugar llamado de Los Castillejos para más tarde pasar a la falda del Cerro de la Cruz con un poblado de época micénica del que se han descubierto restos.
Más tarde la ciudad romana pasará a asentarse en el valle sobre la que a la vez se asentará la ciudad musulmana.

En el año 997 el Gran Almanzor la fortificó, siguiendo bajo la dominación árabe hasta agosto de 1236, en que fue conquistada por Fernando III. Completamente despoblado después de la conquista, el Rey le concedió grandes privilegios y el dictado de lealtad, acogiéndose asimismo al Fuero Real de Córdoba en 1241.

Los Reyes Católicos confirmaron sus privilegios.

En la Guerra de Sucesión permaneció leal a don Felipe V, concediéndole este monarca mercedes y dictados de Fiel en 1717.

Hasta 1844 la aldea de Almedinilla era dependiente del ayuntamiento de Priego de Córdoba. En este año junto con Fuente Tójar se separa de Priego de Córdoba formando término municipal y Ayuntamiento propios.