Coll'affermarsi della dominazione bizantina nell'Italia Meridionale, sorge l'attuale rione Borgo Vecchio e con esso la cittadina si affaccia alla ribalta della vita medievale. Cattedra vescovile di rito greco dall' 887 , accoglie (al tempo della persecuzione della persecuzione iconoclasta proclamata dall'imperatore Leone Isaurico), i fuggiaschi monaci basiliani che, eremiti per vocazione, alloggiarono in alcune grotte, esercitando il loro culto e affrescandole nei modi e nella tecnica di Bisanzio. Arrivati i Benedettini, questi si opposero energicamente all'opera di grecizzazione intrapresa dai Basiliani. La popolazione ben presto si scinde in due fazioni con conseguenti focolai d'insurrezione. Impotente a reprimerli da solo, il governo di Bisanzio si vede costretto a far ricorso ai Saraceni, che allora dominavano la Sicilia, mentre a sua volta il romano pontefice Giovanni III sollecita l'intervento dei Longobardi. Nel 999 Gravina cade nelle mani dei Greci e l'archidiocesi latina di Benevento, creata da Papa Giovanni, viene soppressa, finché nel 1052 con la separazione delle due Chiese elimina ogni motivo di dissidio. Coi Normanni, che l'occuparono nel 1069,la città diventa un feudo con Unfrido (figlio di Accardo e terzo Signore di Gravina), ed ebbe modo di sollevarsi dalla miseria e dall'avvilimento in cui l'avevano gettata il malgoverno bizantino e la ferocia musulmana. Venuta a mancare la discendenza di Roberto il Guiscardo nel Ducato di Puglia, Ruggero II - Gran Conte di Sicilia - la unisce ai suoi stati, nell'intento di formare una sola monarchia alle sue dipendenze. La violenta reazione di tutti i dinasti dell'Italia Meridionale, incoraggiati dallo stesso papa Onorio II, scatena una lotta aspra e tenace, che ha termine con la conquista della città da parte di Ruggero, il quale al ribelle Roberto, figlio d'Unfrido, sostituisce un marchese di stirpe subalpina: Bonifacio, marchese d'Incisa. Con Alberto, figlio di Bonifacio, la città diventa capoluogo di contea.
Morto Alberto, la contea fu devoluta alla Regia Corte e quindi assegnata a Gilberto de l' Aigle, cui successe - dopo appena un decennio - Riccardo de Say, un altro discendente da nobile e storica famiglia subalpina.