La località in cui la chiesa sorge era detta anticamente “casale di Padula”. Secondo il Paglia, essa fu consacrata nel 1096 dal Vescovo Pietro che ripose, sotto l’altare, alcune reliquie di San Crisanzio, dei santi Cosma e Damiano e di Sant’Eustachio, al quale dedicò la Chiesa. Tali reliquie furono rinvenute nel 1282 e trasferite in Cattedrale.
La chiesa, servita da clero greco, fu parrocchia di quel popoloso casale. In seguito, per la carestia e per la peste, nel sec. XIII restò completamente disabitata, essendosi la popolazione trasferita a Costantinopoli. La chiesa appartiene al tipo molto comune in terra di Bari, a pianta rettangolare absidata voltata a botte, interrotta da un breve braccio trasversale contenuto nello stesso perimetro della navata, e cupola all’intersezione. Restaurata nel 1733 fu dedicata alla Madonna delle Grazie dal Vescovo Paolo De Mercurio. Una lapide attualmente conservata nel museo della Pro Loco dice testualmente:
“A DIO OTTIMO MASSIMO QUESTO TEMPIO SACRO AI SANTI PIETRO ED EUSTACHIO,PER VETUSTA’ DEI TEMPI QUASI DISTRUTTO, AFFINCHE’ PIU’ SI ACCENDA LA DEVOZIONE DEI FEDELI CHE OGNI DI’ VI CONVENGONO PER ADORARE QUEST’IMMAGINE DELLA VERGINE, IL CANONICO PENITENZIERE DOMENICO MISURELLI RACCOLSE OBLAZIONI E POSE UN ALTARE IN PIETRA, CHE IL VESCOVO DI GIOVINAZZO PAOLO DE MERCURIO CON SOLENNE RITO CONSACRO’ NELL’ANNO DEL SIGNORE 1733 AI CINQUE DI GIUGNO”.
