Si ritiene che un primitivo nucleo urbano sia esistito fin dal secolo VII nel sito ove vi sono i ruderi della chiesetta di S. Maria di Modugno.
Trovasi questa in un fondo rustico quasi a metà strada tra il convento di S. Domenico e quello dei Cappuccini, ridotta ora quasi tutta in rovina.

Distrutto il paese probabilmente nel secolo IX in qualche incursione saracena, esso fu ricostruito quindi verso il Mille, più ad occidente intorno al preesistente castello Cotta, probabilmente sede del presidio bizantino.

Andò soggetta alle vicende delle varie dominazioni che si susseguirono nel regno di Napoli: Normanni, Angioini, Spagnoli, Austriaci, fino al regno indipendente dei Borboni, con la parentesi dei Napoleonidi, e quindi al regno italico dei Savoia.

Fu soggetta a feudatari dal 1212, quando Federico II la concesse agli arcivescovi di Bari, i quali tranne brevi interruzioni, la tennero in feudo fino al 1386.

Fu sempre sotto Federico II che l'Italia Meridionale acquista un primo piano nell'impero, e divenne fulcro della politica e della cultura.

Seguirono poi altri feudatari finché Ferdinando I d'Aragona, re di Napoli la concesse nel 1464 con Bari e Palo in ducato agli Sforza di Milano, i quali la governarono con saggezza, specie le duchesse Isabella d'Aragona e la figlia Bona Sforza.