Di questo santuario non si conosce la data esatta di costruzione, ma l'ipotesi più accreditata, da circa quarant'anni, suggerisce varie fasi di edificazione tra la seconda metà del XII e la prima metà del XII secolo durante le dominazioni normanna e sveva. La presenza di resti di un affresco (sicuramente il più antico della chiesa) raffigurante un volto di Madonna, di evidente matrice bizantina, accrediterebbe, d'altro canto, una retrodatazione di circa due secoli.

In seguito all'assedio di Gallipoli (1268-1269) da parte di Carlo I d'Angiò, la chiesa aletina fu elevata a sede episcopale e intitolata a Santa Maria de Cruciata e naturalmente a Sant'Agata come la cattedrale di Gallipoli . L'episodio è documentato da una lettera di Papa Giovanni XXII che da Avignone esortava Milezio vescovo di Gallipoli, e tutti i fedeli, a raccogliere fondi per edificare e ricostruire la cattedrale.