Nei cinque secoli successivi alla disfatta dell’Impero Romano d’Occidente, molti popoli stranieri si succedettero al governo di questo territorio: Goti, Bizantini, Longobardi, Franchi, e Germanici. Questo costituì un elemento di innegabile instabilità, ma nello stesso tempo fece sì che i territori murgiani si arricchissero degli apporti di differenti culture che hanno lasciato tracce tutt’oggi visibili.
Sotto i Goti, il territorio murgiano fu interessato dal conflitto tra questi e i Bizantini di Giustiniano e tra il 546-547, Gravina di Puglia fu completamente distrutta e i suoi abitanti, dispersi, si rifugiarono nei pressi delle grotte vicino Spinazzola (già abitazioni trogloditiche).Questo stesso nucleo nel IX secolo, si trasferì sulla riva sinistra della stessa gravina, dando vita alla Civitas Gravinae.(anche Ruvo fu distrutta dai Goti nel 463 d.C.).
Tra il 568 e il 774 d.C. registriamo la presenza dei Longobardi, i quali dopo aver conquistato tutto la penisola italica da nord a sud nel VII sec. d.C. arrivarono , attraverso la via Traiana e la via Appia fino a Taranto e Brindisi.
Forte fu il conflitto tra i Longobardi e la Chiesa che vide ridotti i suoi poteri fino al 662, anno in cui registriamo la conversione in massa di questa popolazione.
Nel VIII sec. d.C il ritorno dei Bizantini, ridiede poteri alla Chiesa. Nel 867 Gravina venne eletta sede episcopale. La cintura tra Altamura, Gravina e Matera serviva ai Bizantini per governare i territori interni (specie durante il tentativo di conquista da parte dei Saraceni), essendo già essi molto forti nel controllo della costa. Nonostante tutto per quarant’anni i Saraceni con continue incursioni dalla costa saccheggiarono e distrussero alcune città dell’interno tra cui: Spinazzola, Gravina, Acquaviva, Matera ed Altamura. Il tutto ebbe fine solo nel 994 con l’assedio di Gravina, che ne uscì vittoriosa.
