Le origini del paese risalgono al XII secolo. Dal registro normanno dei baroni, del sec. XII, si apprende che Corleto era un luogo già abbastanza popolato. Esso si é formato attorno al vecchio castello feudale e le sue case erano poste in maniera tale da'coprirlo e difenderlo da eventuali incursioni esterne.
Alla seconda crociata per la liberazione del Santo Sepolcro parteciparono molti normanni residenti in Basilicata, i quali si raccolsero sotto il comando di Boemondo, Goffredo di Montescaglioso e Roberto, figlio di Tristano di Anzi. Ad essi si riunirono parecchi Corletani. La prova di ciò é data dall'esistenza nella chiesa parrocchiale di Corleto di un avanzo di un'antica croce trasportata, come la tradizione vuole, dalla Siria da vari Corletani che parteciparono alla suddetta crociata. Si tratta, più precisamente, di una pietra prismatica quadrangolare che doveva essere - affenna Enrico lerardi - " la base di una antica croce e che riporta scolpite in ciascuna delle sue quattro facce delle iscrizioni latine e disegni di grande importanza".
Nel 1194 Enrico, figlio di Federico 1, inviò a Corleto Ruggero conte di Andria a sottometterla. Vi fu la distruzione delle case e gli abitanti furono costretti ad abbandonare questo centro. Coinvolto poi nelle vicende di Corradino di Svevia subi a lungo una situazione di crisi. Per quattro anni,dal 1459 al 1462, la zona di Corleto fu sconvolta per le pretese del duca Giovanni D'Angiò sostenuto da molti principi e baroni. Nel 1659 Corleto divenne feudo della Casa Rian'o ma il contagio del 1659 che portò tanta desolazione.
Negli ultimi anni del dominio borbonico assunse una posizione di primo piano quando, centro liberale, il 16 agosto 1860 dichiarò decaduta quella dinastia. Nel pomeriggio, in piazza Castello, ribattezzata del Plebiscito, il generoso popolo di Corleto proclamò solennemente l'Unita d'Italia, scrivendo una delle pagine più belle del Risorgimento. A capo dell'insuitezione fu Carmine Senise che divenne senatore del Regno. Giacomo Racioppi, il grande storico di Molitemo, ricostruisce il clima di quei giorni, evidenziando lo stato d'animo in cui matura l'insurrezione. "All'alba del 18 agosto fra l'entusiasmo generale, le forze rivoluzionarie, agli ordini del colonnello Camillo Bold oni, inviato segreto di Cavour, partono per Potenza.
Lungo il tragitto si uniscono i drappelli di Laurenzana, di Accettura, di Viggiano, di Saponara, di Calvello, di Abriola, di Pietrafesa, di Vietri e di Picerno. Lo stesso giorno, nel capoluogo, viene proclamato il governo provvisorio nel nome di Vittorio Emanuele, re d'Italia e del generale Giuseppe Garibaldi. Dal settembre al novembre del 1860 la cerimonia si ripete in tutti i comuni della Basilicata". Notevole è il contributo di Corleto all'emigrazione d'oltreoceano e forte la sua opposizione al fascismo.
Con il terremoto del 23 novembre 1980 Corleto ebbe il 20% dei fabbricati danneggiati, diverse case rase al suolo (per es. la bellissima casa gentilizia, in via Nazionale, di don Egidio Lacava).