L’origine di questo Palazzo si fa risalire al sec. XIV, anche se le parti attualmente in vista rappresentono il frutto dei rifacimenti del 1586, eseguiti da Pietro Paolo e Bernardo Regna. Questi lavori riguardarono la facciata rivolta su Piazza Cavour, col nuovo portone d’ingresso affiancato da coppie di semicolonne dorico-romane su alto basamento. Il portale è a bugne del tipo toscano solo negli anni successivi, e qui soltanto, si diffuse secondo una tipologia più robusta e pesante.
Nel concio di chiave del portale è scolpito lo stemma nobiliare della famiglia, mentre sulle colonne binate, ci sono due formelle i cui fregi rappresentano i busti dei romani Giulio Cesare e Augusto, incoronati di alloro.
Nel fregio del portale è incisa in lettere romane la seguente dedica:
PETRUS PAULUS REGNA ARCHIPRESB BITONTIN.
ET BERNARDUNUS EIUS FRATER SIBIET AMICIS — MDLXXX VI
All’interno del piano terra ci sono degli archi ogivali che fanno da sostegno alle murature dei piani superiori.
In quest’edificio, come è successo per palazzo Vulpano, le finestre sono state trasformate in balconi. Si può notare un particolare, non del tutto ortodosso nell’architettura rinascimentale: l’attacco della balaustra con le estremità della trabeazione del portale. Il Rinascimento di provincia, del resto, aveva l’abitudine di prendersi delle libertà, per cui in alcuni edifici, anche se di pregio e di grande interesse culturale, si nota la mancanza della mano di un grande maestro.
I Regna, famiglia di origine lombarda, si stabilirono nella città di Bitonto agli inizi del XIII quando Federico II di Svevia, ai nobili Corrado e Bernardo De Castagnea affidò Paolo Regna, un ostaggio preso nelle lotte contro i comuni. I componenti di questa famiglia hanno partecipato direttamente nella vita politica, civile e culturale della città, tanto che Bernardo Regna nel 1384, prese possesso, sotto l’ordine dell’Universitas di Bitonto, della terra di Palo del Colle.