Dai documenti sappiamo che la famiglia Gironda, a Bari dalla fine del Trecento, era originaria della Francia. Il palazzo fu edificato sul finire del Cinquecento anche se compare per la prima volta nel disegno settecentesco di Giovan Battista Pacichelli, illustratore di diverse città del Regno di Napoli, Bari inclusa. Nel XIX secolo, l’edificio passò alla famiglia Milella, nome che ancora oggi campeggia ai lati del portale: Domus Milella, ossia casa dei Milella. Il grande palazzo ingloba alcune preesistenze medievali, ossia case-torri di XI e XII secolo, tipiche architetture che costellano Bari vecchia. Lo stile che delinea l'edificio è tardo-rinascimentale, sono largamente utilizzate decorazioni che richiamano l'antico. Il prospetto si affaccia su strada degli Orefici, un tempo chiamata strada de' Gironda dal nome dei potenti proprietari del palazzo. Lo zoccolo, ossia la parte che si erge direttamente sulla strada, è rivestito dal bugnato: motivo decorativo costituito da blocchi di pietre sporgenti, disposte una accanto all’altra. Questo tipo di decorazione fu largamente utilizzato sul finire del Cinquecento in molti palazzi nobiliari dell’area metropolitana. Il portale è caratterizzato da due colonnine e da un arco che sovrasta l'ingresso. Ai lati si possono ammirare due tondi che incorniciano altrettanti profili, uno maschile a sinistra, uno femminile a destra. I tondi rappresentano un altro forte richiamo all'arte antica, in particolar modo a quella che si manifestò al tempo dell’imperatore Adriano. Altri tondi si trovano sui portali dei palazzi Zizzi, Tanzi e Verrone. Entrando nell’edificio, si può ammirare la scala monumentale in stile neoclassico del XIX secolo. Sul lato che si affaccia sulla chiesa di Santa Teresa dei Maschi, trova collocazione un grande giardino pensile, ingentilito da un loggiato sorretto da colonne.