L'origine del nome della città si perde nella notte dei tempi ed è avvolto da mito e leggende. Una di queste ritiene che la città sia stata fondata da Obolo, capitano generale dell’armata di Teseo, re di Atene, il quale, dopo aver patito tanti travagli per l’ira degli Dei, sbarcato sul suolo italico si trovò sulle sponde di un fiume dove trovò la morte per annegamento il suo compagno di nome Silaro. Obolo, ormai stanco di peregrinare per terre e mari, accortosi della bellezza del luogo e del clima mite, edificò una città imponendole il nome di Ebalo e chiamò Silaro, l’odierno Sele, il fiume, fino allora senza nome, in onore dell’amico morto.

Un'altra leggenda vuole che Eboli sia stata fondata da Ebalo, figlio della ninfa Sebeti e di Telone, re di Capri, menzionato da Virgilio alla fine del VII libro v. 734 dell'Eneide:

"Oebale, quem generasse Telon Sebethide nympha
Fertur, Teleboum Capreas cum teneret, iam senior"

Alcune versioni fanno derivare il nome dal greco Eu bòlos (ευ βώλος) ossia buona zolla: quando i Greci arrivarono ad Ebhura (trascrizione indoeuropea), trovando il nome simile a quello di numerose località pelasgiche della Grecia, la indicarono come "Efiùra katà Kampànian" (Εφύρα κατὰ Καμπάνιαν). Difatti, il nome "Efiùra" (Εφύρα), è l'antico nome di Corinto, "Efira". Un'ulteriore origine del nome potrebbe derivare da "'Ευ πόλις", ossia "Buona città": la π, tramite un processo linguistico di labiovelarizzazione seconda, si sarebbe trasformata nella labiovelare β, dando origine a "Ευ βόλις", che sarebbe sfociato poi nella variante del Latino Medioevale "Ebolus".

Una ricerca più recente associa il nome di Eboli a quello di Ebur, una divinità legata all'oltretomba, il cui culto era diffuso in ambienti di collina, in particolare vicino a corsi d'acqua (fiumi, torrenti) e grotte naturali o scavate dall'uomo. Nella zona denominata Montedoro alcuni scavi archeologici hanno portato alla luce resti di antico altare sacrificale risalente all'epoca pre-indeuropea. Ciò fa ritenere che in quella zona ci sia stato un legame con il culto di Ebur e la presenza dei torrenti Tufara e Tiranna rafforza questa tesi. Si tratta, tuttavia, di ipotesi, non documentate da fonti scritte.

Prima fonte storica riguardo il nome della città risale infatti ad epoca romana, col ritrovamento di un piedistallo, comunemente detto "Stele Eburina", recante l’incisione che il popolo di Eburum si governava con proprie leggi essendo "Municipium" romano, con a capo Tito Flavio Silvano della prestigiosa famiglia Flavia. La scritta sulla stele venne decifrata dal celebre storico tedesco Teodoro Mommsen che risolse il dilemma delle sillabe e delle parole che mancavano studiando la pietra sul luogo. Sulla lapide si legge:

L. D. D. D.
T. FL. T. F. FAB. SILVANO. PATR. MVN.
EBVR. II. VIR. II. QQ. QVEST. ARK. CVR.
REI. FRVMENT. HVIC. COLL. DEND
ROPHORR. OB. EXIMIAM. ERGA.
SE. BENIVOLENTIAM. ET. SPEM. PER
PETVAM. STATVAM. DIGNISSIMO.
PATRONO. POSVERVNT. CIVIS. STA
TVAE. HONORE. CONTENTVS. OB
TVLIT. COLL. SS. HS. VIII. M. N. VT. QVOTANNIS.
NATALI. EIVS. DIE. III. IDVVM. DECEMBR.
CON. FREQVENTENT. (EIVS) STATVAE. DE
DICATIONEM. CON. (II. VIR. I. D. SING.) HS. XX. N.
QQ. II. VIR. AEDILIC. S(ING. HS. XX. N.) ET. CETE.
RIS. CON. DEC. SING. HS: (XV. N. VI. VIR)IS. AVGVS
TALIB. HS. XII. N: COLL. DENDROPHORR. ET.
FAB. SING. HS. MILLE. N. ET. EPVLVM.
PLEBEIS. SING. HS. XII. N. ET. VISCERATIONEM.
DEDICATA. IV. KAL. APRIL.
MARC. STLACCIO. V. A.
STEIAN.

Traduzione:
"Luogo Assegnato per Decreto dei Decurioni a Tito Flavio Silvano, figlio di Tito della tribù Fabia, Patrono del Municipio degli Eburini, Duumviro, e indi per la seconda volta Quinquennale Questore della pubblica Cassa, e Curatore dell’Annona. A costui il Collegio dei Dendrofori, per la grande benevolenza e perpetua speranza verso di sé, eresse una statua qual degnissimo Patrono. Egli, contento dell’onore fattogli, offrì al Collegio suddetto ottomila sesterzi. Affinché poi, ogni anno ai tre degli Idi di dicembre, giorno di sua nascita, in radunanza, si celebrasse la dedicazione della di lui statua, assegnò a ciascun Duumviro di Giustizia sesterzi venti, e altrettanti sesterzi a ciascuno dei Duumviri quinquennali con la potestà edilizia. Ed agli altri in tal guisa: assegnò a ciascuno dei Decurioni sesterzi quindici, ai Sestumviri Augustali sesterzi dodici, al Collegio dei Dendrofori e dei Fabri sesterzi mille ciascuno ed un banchetto. A ciascuno dei plebei sesterzi dodici ed una eviscerazione. Dedicata ai quattro delle Calende di Aprile, essendo Consoli Marco Stlaccio e Vezio Albino."

La stele appartiene all’epoca imperiale, perché l’uso della parola Curatore, nell’epigrafe riferita a Silvano, patrono del Municipio di Eburum, si rapportava al Magistrato dei Municipi e delle Colonie che prima di tale epoca esisteva solo in Roma con titolo di Prefetto (carica creata quando il bisogno lo richiedeva); fu Cesare Augusto che istituì il Magistrato nelle Colonie e nei Municipi. Gli studiosi hanno datato presumibilmente l’evento nel 183 d.C. sotto l’imperatore Commodo.