La mancanza di fonti seriali rende lacunosa e discontinua la cronotassi dei vescovi tarantini nell’alto medioevo; difficile risulta anche individuare per quei secoli la struttura e l’organizzazione interna della Chiesa locale. Si conosce un vescovo di nome Andrea al quale papa Gregorio Magno mandò una lettera, nel giugno del 593, a causa della sua condotta morale poco confacente alla dignità di un vescovo. Lo stesso papa, nel 603, scrisse una lettera al vescovo Onorio, autorizzandolo ad usare il nuovo battistero costruito nella cattedrale ed esprimendo per ciò il suo compiacimento. Al Concilio Lateranense I, celebrato da papa Martino nel 649 per condannare l’eresia del monotelismo, partecipò anche il vescovo di Taranto Giovanni. Nel 680, con la città già sottoposta al dominio longobardo, troviamo un altro vescovo di Taranto, Germano, tra i partecipanti al IV sinodo romano tenuto da papa Agatone.
Nella stessa occasione sottoscrisse una lettera da inviare al VI Concilio ecumenico di Costantinopoli che avrebbe proceduto alla condanna definitiva del monotelismo.
La critica moderna ha collocato tra la fine del VII secolo e la prima metà del successivo l’episcopato di S. Cataldo, patrono della città e della diocesi. La tradizione più antica lo voleva presente a Taranto tra il II e il III secolo mentre un testo del XVI secolo lo indicava come protovescovo consacrato dallo stesso s. Pietro.
È stata messa in dubbio anche la sua origine irlandese a favore di una origine longobarda locale.
Verso la fine del IX secolo ci fu un tentativo da parte dei bizantini di imporre alla città un vescovo greco, ma la pronta reazione del papa Stefano V non permise che la sede vescovile di Taranto cominciasse a dipendere dal patriarcato di Costantinopoli. In un documento del 978 del principe di Capua Pandolfo Capo di Ferro, il vescovo di Taranto appare per la prima volta col titolo di arcivescovo, concesso dal patriarca di Costantinopoli probabilmente qualche anno prima.
Questo titolo però non istituì nessun legame giuridico col patriarcato, né trasformò la diocesi in una metropolia; si deve pensare ad un semplice titolo d’onore. Soltanto alla fine del secolo XI, con la creazione delle diocesi suffraganee di Castellaneta e Mottola, gli arcivescovi di Taranto, col riconoscimento di Roma, divennero metropoliti, ma non se ne conosce la data esatta.
Dopo la separazione tra la Chiesa d’Oriente e quella d’Occidente nel 1054, la Chiesa di Taranto rimase fedele al papato. Era vescovo in quel periodo un normanno, Drogone, il quale nel 1071, durante i lavori di rifacimento della cattedrale, rinvenne il corpo del vescovo Cataldo protettore della città e della diocesi. La definitiva latinizzazione portata dai normanni decretò il distacco
culturale della Chiesa di Taranto dal mondo bizantino. La città nel basso medioevo ebbe importanti monasteri: da ricordare quello benedettino di S. Pietro Imperiale, quello basiliano di S. Vito del Pizzo e quello cistercense di S. Maria del Galeso; vi erano anche due monasteri femminili.