L’esistenza di Modugno è documentata storicamente a partire dall’XI secolo, grazie a un frammento di pergamena del 1021 che riporta un contratto stipulato tra un abitante de loco medunio edi fratelli Giovanni e Mele di Bitetto. La tradizione vuole che il nucleo più antico del paese sorgesse intorno alla chiesa di S. Maria di Modugno.
Presumibilmente, in analogia a quanto risulta per altri centri della zona, l’abitato deve la sua esistenza alla confluenza degli abitanti dei casali sparsi in età altomedievale nel territorio al riparo della Motta (piccola altura su cui pare fosse ubicata una torre di avvistamento).
Le esigenze di sicurezza legate alle incursioni del X secolo da parte dei Saraceni portò così alla nascita del nuovo centro urbano che entrò sotto la giurisdizione della diocesi di Bari, come testimoniano le fonti documentarie.
In età sveva (XIII secolo) il paese era sicuramente feudo degli Arcivescovi di Bari. Bartolomeo Carafa, ultimo arcivescovo a guidare il feudo di Modugno nel XIV secolo, dotò la cittadina di una cinta muraria più robusta di quella precedentemente esistente e fece ricostruire la Chiesa Matrice. Dopo di lui il feudo passò sotto il controllo degli Orsini principi di Taranto.
Nel 1463, estintasi la famiglia del Balzo Orsini, il feudo tornò al demanio e fu affidato agli Sforza signori di Milano.