Costruita romanico nel XII secolo (1158) sulle rovine di un tempietto di origine messapica per volontà del feudatario normanno Roberto Gurguglione, fu ricostruita in stile rinascimentale nel XVI secolo. La chiesa in origine era dedicata all'Assunzione della Vergine Maria e solo più tardi fu intitolata al nome di sant'Eustachio martire.

 

La primitiva chiesa, ormai malandata e insufficiente alle necessità dell'aumentata popolazione, fu ricostruita a partire dal 1529, quando era feudatario di Acquaviva Giovanni Antonio Donato Acquaviva. Ultimata e aperta al culto nel 1594 durante il governo di Alberto Acquaviva, la chiesa fu consacrata nel 1623 in onore di sant'Eustachio dall'arcivescovo di Bari e Canosa Ascanio Gesualdo.

 

Sin dall'origine fu detta "palatina", cioè appartenente al re (dal latino palatium che significa "palazzo reale"), probabilmente per preservarla dalle mire degli arcivescovi di Bari. Le chiese palatine per la loro giurisdizione non dipendevano dall'ordinaria potestà ecclesiastica, ma dal sovrano, il quale di solito nominava chierici di suo gradimento e da lui remunerati. Attualmente sul suolo pugliese se ne contano quattro: la cattedrale in questione ad Acquaviva, la cattedrale di Santa Maria Assunta ad Altamura, la Basilica di San Nicola a Bari e il santuario di San Michele Arcangelo a Monte Sant'Angelo.

 

Il 13 gennaio 1859, dopo una sosta ad Acquaviva e di passaggio per Bari per il matrimonio del principe ereditario con Maria Sofia di Baviera, il penultimo re del Regno delle Due Sicilie Ferdinando II assiste alla messa piana nella cripta della cattedrale.

 

La facciata principale a cuspide, tripartita da lesene e divisa in due ordini (il primo è corinzio, il secondo dorico), è nell'insieme di stile rinascimentale, mentre il resto delle facciate ha uno stile architettonico che richiama il romanico pugliese.

 

Al centro del prospetto frontale di apre un rosone rinascimentale, tendente al manierismo, composto da sedici colonnine disposte a mo' di raggi e collegati da archetti. Sotto questi ultimi è presente un'alternanza di valve di conchiglia e teste di puttini alate. Dal centro del rosone sporge una figura litica fitomorfa.

 

Il portale principale possiede un protiro finemente decorato. Le colonne che sorreggono il frontone di esso poggiano su due leoni stilofori.

 

I portali laterali sono sovrastati da due nicchie oggigiorno vacanti. Ognuna di esse ha installato sul vertice un bassorilievo raffigurante un'antica versione dello stemma di Acquaviva delle Fonti.

 

L'archivolto del suddetto portale presenta un bassorilievo raffigurante la conversione di sant'Eustachio.

 

La facciata termina superiormente con un'ampia quinta triangolare, nel cui mezzo è infissa una lapide che ricorda il nome del feudatario Alberto Acquaviva. Sui tre vertici sono collocate sculture in pietra, rappresentanti san Pietro e san Paolo nei laterali e Maria Vergine seduta con il Bambino sulle ginocchia su quello centrale.

 

L'interno, con pianta a croce latina, è suddiviso in tre navate con copertura a volta. La volta maestra è sostenuta da grandi archi, che poggiano su pilastri in pietra con delle colonne a metà sporgenza in direzione dei suddetti archi. I muri perimetrali presentano delle colonne sporte a metà, sormontate da finti pilastrini sostenenti degli archetti. Le volte, come pure i pilastri e le colonne, sono ornati da stucchi. L'altare maggiore, risalente al XVI secolo, è dedicato alla Vergine di Costantinopoli. Le tele ad olio, che ornavano la chiesa primitiva, durante i lavori di ricostruzione furono donate alle chiese di San Domenico, di Santa Maria Maggiore, Sant'Agostino e Santa Maria della Libera. L'organo monumentale fu donato alla chiesa dal vescovo Tommaso Cirielli.

 

La cripta, probabilmente costruita insieme alla chiesa primitiva, è a forma di parallelogrammo ed è coperta da ventiquattro volte a crociera, sostenute da quattordici colonne marmoree di ordine ionico al centro e da pilastrini poco sporgenti dai muri perimetrali. Addossati al muro posteriore sono tre pregevoli altari. Sul primo di essi è collocato un quadro di sant'Eustachio, ai cui lati poggiano su mensole due sculture in marmo, che rappresentano rispettivamente la moglie del santo, Teopista, e il gruppo dei figli Teopisto e Agapio.

 

L'altare centrale, costruito nel 1693 e dedicato al Santissimo Sacramento, è circondato da balaustre in breccia di Francia. Il paliotto, tutto in doppia lamina d'argento, presenta un tempietto ottagonale sormontato da una cupoletta e diviso in tre piani ornati da varie figurazioni. Sull'altare risalta un grande tabernacolo.

 

Il terzo altare, realizzato nel 1753 e dedicato alla Vergine di Costantinopoli, è rivestito interamente di lamine d'argento. Su di esso domina un dipinto attribuito a Francesco Palvisino raffigurante la suddetta Madonna che tiene in braccio il Bambino. Le immagini della Madonna e del Bambino sono ornate da due corone auree.

 

Sulla cantoria in controfacciata si trova l'organo a canne, costruito nel 1905 da Carlo Vegezzi Bossi; lo strumento, nel corso del tempo, è stato oggetto di importanti restauri e rifacimenti, tra cui quello del 1968, condotto da Leonardo Consoli, e quello del 2001-2004 condotto dalla ditta organaria Continiello, durante il quale, tra le altre cose, è stata rimossa la cassa lignea, opera dell'acquavivese Paolo Tritto ed è stata fornita la nuova consolle mobile.