Le origini di questo borgo risalgono a quando i Greci colonizzarono la valle del Basento tra il V e il VI secolo avanti Cristo che portò alla fondazione di un centro urbano chiamato Maudoro, ovvero “mondo d’oro”. Nel X secolo, a causa delle invasioni saracene, gli abitanti si trasferirono in quello che oggi conosciamo come Castelmezzano.

Fu occupato dai longobardi e in seguito dai Normanni, che costruirono un castello chiamato “Castrum Medianum”, che sta per “castello di mezzo”. Fu chiamato così perché costruito tra i castelli di Pietrapertosae Albano, da cui deriva il nome originale della città.

Castelmezzano, dominato anche dagli Angioini, conobbe periodi difficili e nel 1310, venne acquisito dalla Diocesi di Potenza e in seguito da quella di Acerenza. Gli Aragonesi lo conquistarono tra il XIV ed il XVI secolo e diedero a molti proprietari terrieri, parti della città come feudo.

Fu governato dalla famiglia De Leonardis per circa un secolo a cavallo tra il 1500. Nel XIX secolo quando era sotto il dominio della famiglia De Lerma, fu vittima della piaga del brigantaggio e alla fine del secolo molti si trasferirono oltreoceano.