Abitata fin dall’età neolitica (come testimoniano i resti di armi in rame e altri reperti), Lacedonia fu chiamata  prima  Akudunniad dagli Osci e  poi  Erdonea  forse dal nome di un conquistatore. Dopo frequenti distruzioni, fu riedificata dai Romani, prese il nome di Aquilonia, venendo inclusa nella Tribù Galeria.  Si chiamò, in seguito, Al Cidonia e Cedogna fino al 1800. Infine, prese l'attuale denominazione.

L’immagine più antica dello stemma di Lacedonia era l'Aquila; lo stemma della Cicogna apparve per la prima volta in un manoscritto del 212 a.C.

Le tracce più visibili della sua antichità ci portano nel 293 a.C. ad Aquilonia (oggi Lacedonia), dove, in località detta «Chiancarelle», fu combattuta la battaglia decisiva della terza guerra sannitica e la formidabile Legione linteata fu annientata dai Romani. Il Corso Aquilonese, sua strada importante, ne richiama l'antico nome.

Sotto Roma, era un importante Municipio, come attestano le lapidi trovate sul posto, stele, monete, ricordi funerari, un tempio alla dea Iside, sulle cui rovine fu costruita la chiesa di Santa Maria della Cancellata; la città aveva la piscina, le terme, l'anfiteatro, lavatoi, giardini pubblici, una fornace e, in località Capi dell’acqua, una mutatio (stazione destinata al cambio di carri e cavalli). La via principale del paese è chiamata Corso Augustale in memoria dell'imperatore Augusto.

Con l'avvento del Cristianesimo, Lacedonia fu possesso dei monaci benedettini, ai quali era stata donata dall'imperatore Giustiniano nel 5 I 7 d.C.

Passò sotto il dominio dei Longobardi, dei Conti di Conza, dei Normanni; fu feudo dei Balbano, casato spodestato da Carlo d'Angiò, re di Napoli. In seguito, passò agli Orsini, principi di Taranto e Gabriele Orsini ricostruì la città distrutta dal catastrofico terremoto del 5 dicembre 1456.

     Il Patrono del paese è San Nicola di Bari (6 dicembre); il Compatrono è San Filippo Neri (26 maggio).

Fu teatro, nel 1486, della famosa Congiura dei Baroni.

Baldassarre Pappacoda, proprietario del castello nuovo (1501), fu sepolto nella Cattedrale insieme con la moglie Donna Cornelia D'Accio.

I Pappacoda tennero il feudo fino al 1566, quando fu venduto ai Doria, signori di Melfi, che vi rimasero fino al 1806 anno in cui Napoleone Bonaparte sancì la fine del Feudalesimo.

Nel 1820, in località La Tagliata, fu rinvenuta una 'scure consolare".

Nel 1841, Don Vincenzo Franciosi fece demolire l'antico arco gotico, situato presso l’Episcopio.

Nel 1859, Don Vincenzo Palmese, fratello del Canonico Pasquale, portò a termine costruzione del Carcere mandamentale.

Dopo il 1860, nel territorio di Lacedonia, operarono briganti tristemente noti, quali Petrozzi, Marciano Lapio, Caruso, Sacchitiello, Crocco, Ninco Nanco.

Il 17 gennaio 1875 il Collegio di Lacedonia elesse suo deputato, al terzo ballottaggio Francesco De Sanctis; un'ampia piazza, un austero monumento, una spaziosa strada il glorioso Istituto Magistrale incarnano e testimoniano l'azione e il pensiero del sommo critico e maestro. Era sindaco di Lacedonia il dott. Vincenzo Saponiero.

Nel 1912 comparvero le prime automobili.

Nel 1924 fu realizzata la pubblica illuminazione dal Cav. Gerardo Alfonso Vigorita.