Per tutto l'Alto MedioEvo Eboli rimane "vicus eburi" ai piedi di Montedoro.
Il primo documento cartaceo che cita la città è dell'anno 869: è il Codice Cavense (Codex diplomaticus Cavensis) da cui si apprendono i nomi dei componenti di una famiglia longobarda ebolitana: "Gariperga, è moglie d’Ermenardo servo di Palazzo, è figlia di Gariperto che fu anch’egli servo di Palazzo a Eboli, Gariperga passa al servizio di Landelaica moglie del principe salernitano Guaiferio insieme a quattro figli maschi e tre femmine".
L'avvenimento ha interesse storico e archeologico in quanto il termine "Servo di Palazzo" non si confronta con la concezione schiavistica del mondo romano o con quella, più blanda, basso medievale, di uomo al servizio personale di qualcuno; egli era piuttosto un funzionario del Principato Salernitano il cui compito consisteva nella partecipazione all'impostazione dell'andamento sociopolitico del centro, come appartenente alla categoria di amministratori, i ministeriales ".
Il palatium sede del potere ad Eboli, nel periodo longobardo doveva sussistere o sulla collina dove poi si fonderà il castello normanno, oppure sulla collina dove sorgerà il complesso conventuale di San Francesco, oppure ancora in un punto posto tra le due colline. In ogni caso, lungo la via G. Genovese, verso nord, fino all'angolo di via A. Vacca si può osservare la presenza di un muro in conci di pietra squadrata commista a laterizi, che offre molteplici analogie con costruzioni longobarde come la cinta di Benevento o i muri del castello di Salerno. Il sito riceverà, tuttavia, la sua specificazione urbanistica soltanto nel 1047, quando la comitissa Urania offre alcune terre "foris castello Evoli illorum comitato" (al di fuori della città fortificata di Eboli che è loro contea) alla chiesa di S. Nicola di Gallocanta di Vietri sul Mare; tra i confini delle proprietà, un posto chiamato "li Barbuti": con questo documento la città viene indicata per la prima volta come castellum.
Sul tramontare del IX secolo, si fondarono, nella Campania longobarda, molti monasteri basiliani, così chiamati i primi seguaci di S. Basilio (330-379 d.C.), ma anche tutti i monaci cattolici di rito bizantino non solo presso le grandi città della costa, ma anche nell'entroterra. Ad Eboli, ben presto, dovettero giungere questi monaci, insieme a gruppi di laici, che si portarono numerosi nella nostra città e vi rimasero stabili, come testimoniano la denominazione della parrocchia di S. Nicola de Graecis, detta appunto S. Nicola de Schola Graeca, la chiesa dei SS. Medici Cosma e Damiano, la chiesa e il monastero di S. Giovanni Gerosolimitano.