La primera constancia que hay del Lucena Club de Fútbol data de los años 40, equipo que tras jugar varios años en categoría Regional en el Estadio de la Fuensanta consiguió el ascenso a Tercera división en la temporada 46-47 con Antonio Escudero Rueda como Presidente. Poco duró la alegría puesto que tan solo un año más tarde volvió a descender , desapareciendo por problemas económicos en 1951.
No tarda en nacer en la localidad un nuevo equipo, la Unión Deportiva Lucentina, presidido por Juan Velasco Conde y con equipación totalmente blanca. Tras 3 años consecutivos jugando en Tercera División (56-57 a 58-59), termina por perder la categoría a Primera Regional, donde milita hasta 1968 que acaba desapareciendo nuevamente fruto de una profunda crisis económica.
La Unión Deportiva Lucentina fue el equipo que existió hasta 1956, llegando a militar en 3ª División con indumentaria totalmente blanca y en el Estadio de la Fuensanta. Entre 1956 y 1967 hubo un paréntesis de 11 años en el que no hubo fútbol oficial en Lucena, sólo diferentes equipos no federados que disputaban encuentros amistosos.
Fue ya en 1967 cuando Narciso Correal y Pepe Romero (éste último tuvo un destacado papel en el club como Delegado) fundaron el Atlético Lucentino , compitiendo al año siguiente en Segunda Provincial (equivalente a Preferente) y utilizando inicialmente el Estadio de la Fuensanta que poco después pasó al Campo del Instituto hasta la inauguración del Estadio «Miguel Álvarez de Sotomayor» en octubre de 1970. Este campo tomó el nombre del alcalde franquista que lo mandó construir y con la democracia pasó a llamarse Estadio Municipal.
El primitivo Atlético Lucentino era totalmente local con jugadores como Bergillos, Angelín, Cantero (Piojo), Martínez, Jose, Juan Carlos Rivas (Coco), Juan Maillo y el capitán Agustín Tubío (actual jugador veterano de badmington), siendo su primer técnico Manolo Valverde. A partir de 1970 empezaron a llegar técnicos y jugadores cordobeses que al principio jugaban junto con los de la localidad, pero poco a poco los jugadores locales fueron marginados.
En 1973 el Atlético Lucentino con un equipo formado exclusivamente por cordobeses y dirigido por Bernardo Palacios ascendió tras una liguilla a Primera Regional (equivalente a Tercera División), fue el llamado «equipo de los Cabezuelos» en el que destacó el goleador Pepe Cabezuelo junto con su hermano Manolo, además del meta Pajarito, Juani (pata de hierro) y Joaquín. El presidente de esta primera etapa fue Alfonso Jiménez, contando con la presencia del utillero Antonio Guardeño «Pola» (que actualmente aún contínua con esa misma función) y de Manuel Palacios que estuvo más de 20 años como ATS y directivo.
En 1974 el equipo compitió en Primera Regional en el grupo de Andalucía Oriental con el Alvear de Montilla y equipos de Granada, Jaén, Málaga y Almería. Al no haber acuerdo económico con los jugadores cordobeses que lograron el ascenso, se trajo un equipo totalmente de Málaga que jugó en Primera Regional dos temporadas y en 1975 logró el ascenso a la recién creada Regional Preferente, grupo único con equipos de las 8 provincias andaluzas. Tan sólo se mantuvo la categoría un año ya que el equipo descendió a Primera Regional.
Tras un inicio con la equipación celeste y pantalón blanco a la que se ha vuelto en la actualidad, el equipo recuperó los colores de la antigua U.D. Lucentina y casi siempre vistió de blanco, salvo a finales de los 70, en que por el auge de la autonomía andaluza, vistió un breve período con camiseta verde y pantalón blanco.
El equipo de «los malagueños» fue muy popular entre la afición por su buen juego, existiendo en ese período hasta tres presidentes: Antonio Chacón, Rafael Serrano Pino y Pepe Borrego. Como entrenadores en esa etapa destacar al argentino Evaristo Sande, Botella, Madroñero y Andrade y jugadores como los porteros Villamuela y López, Kopa, Cuadros, Callejón, Salas, Barrionuevo(el Indio) y, sobre todo, los hermanos Medina (Paquito y Fernando). Se significa que en esta etapa sólo había un jugador lucentino, Salva (Candil), delantero de clase y habilidoso, marginado por los entrenadores malagueños.
En 1976 tras el descenso a Primera Regional se vuelve a contar con jugadores cordobeses y se juega en el grupo de Andalucía Occidental, retornando el equipo a la Preferente con Fernando García como entrenador, y Luis Beato García como presidente hasta 1980.