Sorto tra la fine del XV e l'inizio del XVI secolo nell'area precedentemente occupata dal Convento dei Celestini, fu dapprima residenza dei Guevara, feudatari di Potenza, poi dei conti Loffredo, dopo la trasformazione del castello in ospedale. All'inizio del XIX secolo, il palazzo ospitò l'Intendenza di Basilicata; intorno al 1825 divenne sede del "Real Collegio", istituito con decreto di Luigi Bonaparte per l'istruzione superiore dei giovani della Provincia di Basilicata. Nel 1850 un decreto del re Ferdinando II affidò il Collegio ai Gesuiti, che lo gestirono fino al 1860. Dopo l'Unità d'Italia, l'Istituto fu denominato "Real Liceo" e intitolato dapprima a Salvator Rosa, poi a Luigi La Vista ed infine a Quinto Orazio Flacco. Ancora nel XX secolo, Palazzo Loffredo ha ospitato il conservatorio di musica Gesualdo da Venosa ed il convitto nazionale Salvator Rosa.
Nel corso dei secoli, il Palazzo ha subito numerosi interventi di restauro e consolidamento che, con ampliamenti e sopraelevazioni, hanno trasformato la struttura originaria. La facciata principale si articola intorno ad una corte racchiusa dalle due ali laterali dell'edificio. Il grande portale d'ingresso ad arco a tutto sesto precede un secondo portale architravato, più piccolo. Al di sopra del portale si apre un loggiato a sei fornici con mostre in pietra liscia.
L'edificio presenta una buona distribuzione dei locali su una corte interna; il collegamento verticale è assicurato da uno scalone in pietra, che si sviluppa nell'ala destra. Il secondo piano, cui si accede attraverso una scalinata interna nell'ala destra dell'edificio, si apre sul cortile con un loggiato finestrato.
Palazzo Loffredo attualmente è sede della Soprintendenza per i Beni Archeologici della Basilicata, del museo archeologico nazionale "Dinu Adamesteanu" e della galleria civica dove hanno luogo importanti manifestazioni culturali.