Il "municipium" di Silvium rispecchiava i criteri organizzativi romani: i "duoviri aediles", funzionari con poteri di ordinanza e polizia analoghi al moderno sindaco, presiedevano alla curia, ossia il senato locale [Nard., p. LXXII].
Nel III secolo d.C., la città si spostò nella vallata della "gravina", da cui prese il nome [cfr. Nard., p. LXXIV].
Sotto il dominio longobardo, Gravina, ebbe "un'ampia autonomia amministrativa che permetteva di dedicarsi proficuamente alle molteplici attività produttive [...]" [cfr. A. Papagna, L'incursione saracena a Gravina nel 977, in "Istituzioni, uomini e cultura, cit., pp. 35-6; P. Corsi, Aspetti e problemi del popolamento ai confini apulo-lucani in età bizantina, in "Il popolamento a Botromagno-Gravina. Vedi Gravina Itinerario III, cit., 1987, p. 81-2; Nard., p. LXXVI].
Dal XIII secolo Gravina ebbe i suoi primi sindaci e sino al 1597 la città elesse sindaco e decurioni secondo consuetudini (che trovavano fondamento nei capitoli del duca di Calabria del 1472, del re Ferdinando del 1478 e nel riconoscimento dei duchi Orsini dal 1501) secondo le quali il giorno 26 del mese di agosto il commissario regio (rappresentante dello Stato) convocava il consiglio comunale composto dal sindaco e dagli eletti in carica, dal sindaco e dai consiglieri eletti l'anno precedente, e da 24 nuovi capi famiglia portati dai gruppi consiliari. In tal modo si ottenevano 48 membri, rappresentanti i nobili ed il popolo, che eleggevano il nuovo sindaco (la carica era annuale o rinnovabile due anni dopo l'ultimo incarico), 12 consiglieri e 24 ufficiali amministrativi tra cui: il mastro d'atti (ufficiale giudiziario), il cancelliere (attività di segretario comunale), l'erario, il camerlengo (custode della città), il baiulo (presiedeva la polizia di campagna), il catapano (responsabile di polizia urbana e dell'annona) [cfr. A. Manzella, De iure civico gravinensi, in Archivio Unico Diocesano Gravina, Fondo Capitolare, I K 27; Nard., p. LXXXI].
La storia di Gravina vide il succedersi di molti feudatari. Dal 1069 al 1080 il feudo fu assegnato ad Abagelardo prima, e ad Accardo poi, entrambi figli di Unfrido, conte di Puglia e fratello di Roberto il Guiscardo. Dal 1080 al 1116 il feudo passò ai discendenti di Accardo, per finire dal 1116 al 1133 a Roberto, figlio di Goffredo di Conversano [cfr. Nard., pp. 31-47].
Nel 1133 feudatario di Gravina fu Bonifacio Marchese d'Incisa che lo tenne sino al 1144 quando passò al figlio Manfredi, alla cui morte, nel 1148, subentrò la moglie Filippa e poi nel 1155 il figlio Silvestro. Nel 1157, morto senza eredi Silvestro, il feudo passò al conte Alberto, fratello di Manfredi e figlio di Bonifacio d'Incisa, e lo tenne sino al 1160, anno in cui morì senza lasciare discendenti diretti. [cfr. Nard., pp. 49-55]
La contea di Gravina, perciò, entrò a far parte, per brevissimo tempo, della Regia Corte che però l'assegnò repentinamente, nel 1160, al conte Gilberto di L'Aigle contestualmente alla nomina di Gran Connestabile di Puglia e del Principato di Capua [cfr. Nard., p. 57].
In seguito allo spodestamento del conte Gilberto, la contea di Gravina passò a Riccardo De Say nel 1169 e fino al 1178 data in cui, essendo defunto, passò alla moglie Teodora e successivamente al figlio Tancredi che la tenne sino al 1191. Dopo una parentesi di qualche anno in cui Gravina fu devoluta alla Regia Corte, il feudo tornò in possesso dei De Say dal 1195 al 1223 [cfr. Nard., pp. 60-69].
Con la morte di Federico II di Svevia il feudo viene assegnato, nel 1250, al figlio Manfredi che lo terrà sino al 1266 [cfr. Nard., p. 77].
Con l'avvento degli Angioini, il feudo di Gravina, dopo diversi passaggi, nel 1300 giunse ad Elisabetta, figlia di re Carlo I d'Angiò; poi nel 1302 andò a Pietro, figlio di re Carlo II d'Angiò, che lo tenne sino al 1306. Dopo questa data, e sino al 1380, Gravina appartenne ai suoi discendenti [cfr. Nard., pp. 89-152].
Dal 1380 al 1816 Gravina fu in mano alla famiglia degli Orsini [cfr. Nard., pp. 153-298].
Il toponimo ha assunto la forma attuale con un regio decreto del 1863, deriva chiaramente dalla Gravina su cui sorge l'abitato (gravia da «grava», voce prelatina). La città nelle mani degli Angioni fu infeudata da diversi signori, tra cui gli Orsini, che ne conservarono il possesso dalla prima metà del quattrocento sino all'inizio dell'Ottocento.