Le origini della cittadina sono controverse, ma la teoria più accreditata fa derivare il borgo da un insediamento romano denominato Vicus Mendicoleius; pare addirittura che appena fuori del borgo vi sia una piccola chiesetta (detta del Rosario) sorta su un tempio pagano dedicato a Giunone[senza fonte]. Nel VIII secolo pare avvenne l'insediamento di monaci Basiliani di origini bizantine o bulgare sulla rupe del castello. Forse la chiesa di San Nicola che svetta sul borgo, risalente al IX-X secolo, è opera conseguente allo stabilirsi di questi predicatori[senza fonte].
All'incirca in tale periodo il borgo è citato col suo attuale nome che pare derivi dalle scure acque di un lago appenninico situato nei dintorni e poi scomparso. Il borgo viene circondato nel IX-X secolo da mura e torri di cui ancora restano visibili incantevoli tracce. Di queste opere è molto suggestiva la porta di ingresso al borgo denominata "Porta di Ferro" la cui parte in pietra è stata rifatta nel 1552, al di sopra della porta c'è lo stemma della città post-feudale: San Michele Arcangelo che uccide il drago.
A partire dal 968, i suoi territori, costituirono una delle turme del thema di Lucania.[2] Nel periodo medievale, la cosiddetta "terra" di Lagonegro fece parte, della Contea di Lauria. Passò successivamente nel 1463 a Vinceslao Sanseverino, dodicesimo conte di Lauria. Non avendo figli maschi ammogliò sua figlia Luisia con Barnaba Sanseverino, fratello di Roberto principe di Salerno, dandole in dote il suffeudo di Lauria consistente in Lauria, Ursomarso, Layno, Castelluccio, Trecchina e cedette le sue ragioni sopra Torturella, Cuccaro, Lagoniro, Rocca, Policastro, Rivello, Scalea e Bervicaro.
L'11 agosto del 1498 il re Federico donò Lagonegro a Gaspare Saragusio, devoluta per ribellione di Guglielmo Sanseverino, la di cui figlia Giovanna la vendé poi a Vincenzo Caraffa. Nel 1548 il Caraffa la vendé a Giacomo Cossa col patto di retrovenderla. Nel 1550 il Vincenzo Caraffa cedé il dritto di ricomprarla per ducati 5000 a Luigi Caraffa, il quale, acquistò poi per ducati 20.000. I cittadini però nel 1559 si ricomprarono, divenendo così città demaniale[senza fonte].