L’origine della città è incerta, forse edificata dagli Osco – Sabelli, in contrada Murate, sulla riva sinistra del Basento. Strabone e Plinio annoverano Potentia tra le più antiche città libere ed indipendenti della Lucania, fino a quando Roma non iniziò la sua politica di espansione. La città fu conquistata dai Romani e da municipium, fu ridotta al rango di praefectura prima e poi di colonia militare per aver aiutato Annibale, ma si era mostrata ostile anche nelle guerre tra Romani e Sanniti prima e tra Roma ed i Bruzi. Durante l’impero romano essa raggiunse un notevole livello di ricchezza diventando uno dei centri più importanti della regione. A quell’epoca la città si estendeva sulla riva sinistra del Basento, circa 150 mt più in basso della città odierna. Nel Medio Evo la città si spostò verso le montagne e giunse fino agli 800 mt sul livello del mare. Nel 402 d.C. fu conquistata dai Goti guidati da Alarico e nel VI secolo d.C. i Longobardi di Alboino la annessero al Ducato di Benevento. Nell’847 entrò a far parte del Principato di Salerno e ne seguì le sorti. Vi giunsero allora i Bizantini che dettero alla regione il nome di Basilicata dai basilici o governatori che l’amministrarono e, in seguito, i Normanni sottomisero la città e tutta la Basilicata per unirla alla Calabria ed alla Sicilia. Nel tempo dei Normanni la regione perse definitivamente il nome di Lucania per assumere quello di Basilicata; in tale epoca le scorrerie dei Saraceni minacciarono anche una città come Potenza, lontana dalle coste ed arroccata sui contrafforti dell’Appennino all’interno. Presso Potenza una località denominata Campo Saraceno conserva nel nome il ricordo delle incursioni arabe. Nel 1137 fu conquistata dall’imperatore Lotario. Nel XIII secolo fu governata dagli Svevi, ma nel 1269 Carlo I d’Angiò, per mano dei suoi fedelissimi Conte di Belcastro e Ruggiero Sanseverino, conte di Marsico, infierì sui potentini ritenuti ribelli e sul centro abitato che, per gran parte, fu raso al suolo. A far precipitare ancor più le cose contribuì il terremoto del 18 dicembre 1273 che distrusse la città. Nel 1301 il territorio fu trasformato in feudo e dato al conte Giovanni Pipino. Il feudo passò poi a Ugo Sanseverino ed alla famiglia Origlia. Agli inizi del XV secolo la città fu conquistata da Francesco Sforza che la donò a Michele Attendolo di Cotignola. Successivamente fu governata da Alfonso d’Aragona, dalla famiglia Guevara e dalla famiglia Loffredo. Nelle lotte di predominio che seguirono tra Francesi e Spagnoli per la divisione del regno nella seconda metà del ‘600, tutto il Mezzogiorno d’Italia divenne Vicereame spagnolo. Anche Potenza fu teatro di moti di intolleranza popolare antispagnola che vennero facilmente repressi e che portarono all’insorgenza di fenomeni di violenza nelle sue campagne, sempre più spopolate. Nel 1694 un altro violento terremoto la distrusse quasi per intero e ben poco fu fatto dai dominatori spagnoli in favore delle popolazioni e per la ricostruzione della città. Cessata la dipendenza della Spagna, nel Settecento in Italia Meridionale arrivarono i Borboni, prima dinastia italiana dopo tanto succedersi di case regnanti straniere. Nel 1799 fu proclamata la repubblica Partenopea sostenuta dalle armi di Francia; il re si rifugiò in Sicilia e Potenza fu tra le prime città del sud che alzò l’albero della libertà, con la guida del vescovo Andrea Serrao. Potenza combatté valorosamente contro le truppe del cardinale Fabrizio Ruffo intervenute per "restaurare" l’ordine ed il primo a cadere fu proprio il vescovo. Sotto il successivo dominio francese Potenza fu elevata alla dignità di capoluogo della regione. Dai Francesi, soprattutto per merito di Murat, furono molto migliorate le vie di comunicazione interne e con le regioni limitrofe, migliorata l’istruzione ed introdotte nuove norme igienico-sanitarie quali l’istituzione dei cimiteri fuori dai luoghi abitati. La fine del periodo francese portò alla ricomparsa del brigantaggio, che già aveva provocato orrore e sangue dopo la reazione del 1799. Nell’autunno del 1846 il re Ferdinando si recò in visita a Potenza. Protagonista assoluto della ribellione del 1848 fu a Potenza Emilio Maffei, che riunì in città nel Palazzo Loffredo il 5 giugno i delegati delle Province confinanti, i quali sottoscrissero un memorandum a sostegno e difesa della libertà, ma la repressione fu dura. Il terribile terremoto del 1857 distrusse ancora una volta gran parte della città. Il 16 agosto del 1860 il capoluogo lucano si sollevava in armi (fu la prima città dell’Italia meridionale ad insorgere contro i Borboni) ed il 18 dello stesso mese veniva proclamata l’unione al Regno d’Italia sotto lo scettro di Vittorio Emanuele II di Savoia. Con questo segnale, Garibaldi, al di là dello Stretto di Messina, in attesa di eventi, si rincuorò e lasciò la Sicilia. In una lettera fu proprio lui a raccontare l’episodio del grande, primo contributo del Sud all’Unità d’Italia.

La città venne distrutta dal terremoto del 23 novembre 1980 che colpì vaste zone della Campania e della Basilicata. È stato uno dei sismi più intensi e devastanti che abbiano colpito il territorio italiano nel XX secolo, con circa 300 paesi distrutti o danneggiati ed oltre 3000 vittime.

La città è sempre stata interessata al fenomeno dell’emigrazione, soprattutto verso Roma, ma anche verso le città del Nord.