Secondo un'antica tradizione, attestata già all'epoca di Gregorio di Tours (fine VI secolo), la chiesa di Narbona fu fondata verso la metà del III secolo da san Paolo, evangelizzatore della regione. Solo più tardi, attorno al IX secolo, venne qualificato come discepolo degli apostoli e identificato con il proconsole Sergio Paolo di cui parlano gli Atti degli Apostoli (13,6-12[1]).[2]
Primo vescovo storicamente documentato è Ilario, menzionato in alcune lettere pontificie tra il 417 e il 422. Grande figura di vescovo dei primissimi secoli fu san Rustico, già monaco dell'abbazia di Lerino, governò la chiesa narbonese per oltre trent'anni affrontando l'invasione dei Visigoti di Teodorico I (436) che occuparono l'intera regione con il lungo assedio di Narbona (che resistette fino al 462); cercò di consolidare e rafforzare il cattolicesimo dall'invasione visigota ariana e a lui si deve la ricostruzione della cattedrale, distrutta da un incendio nel 441, nella quale fu sepolto.
Nel VI secolo l'arcidiocesi cedette porzioni di territorio a vantaggio dell'erezione delle diocesi di Elne e di Carcassonne.
Papa Pasquale II accordò invece agli arcivescovi di Narbona la primazia sulla provincia ecclesiastica di Aix, con il titolo di primate della Gallia Narbonese.[3]
Questa situazione durò fino alla prima metà del XII secolo, quando la provincia ecclesiastica ritornò alla situazione precedente.
La cattedrale carolingia, dedicata a due santi di origine spagnola, Giusto e Pastore, fu ricostruita dal vescovo san Teodardo nella seconda metà del IX secolo e completamente riedificata a partire dal XIII secolo.
Tra il XIII e il XIV secolo la provincia ecclesiastica subì importanti modifiche. Nel 1295 venne eretta la diocesi di Pamiers, che fu suffraganea di Narbona fino al 1317. In quest'anno fu eretta la diocesi di Limoux, con territorio ricavato da quello di Narbona, ma ebbe vita molto breve ed era già soppressa nel febbraio 1318. Sempre nel 1317, per meglio combattere l'eresiacatara, Tolosa fu elevata al rango di arcidiocesi metropolitana e dal suo territorio furono ricavate ben 6 diocesi suffraganee. Per compensare la perdita di Tolosa e di Pamiers, nel 1318 Narbona cedette porzioni di territorio a vantaggio dell'erezione delle diocesi di Alet e di Saint-Pons-de-Thomières, che divennero sue suffraganee. Infine nel 1694 anche la nuova diocesi di Alès entrò nella provincia ecclesiastica di Narbona, che, allo scoppio della rivoluzione francese, comprendeva 11 suffraganee: Elne, Carcassonne, Béziers, Lodève, Agde, Montpellier (l'antica Maguelonne), Nîmes, Alet, Alès, Saint-Pons-de-Thomières e Uzès.
In seguito al concordato con la bollaQui Christi Domini di papa Pio VII del 29 novembre 1801 l'arcidiocesi fu soppressa, contestualmente a 6 delle sue suffraganee; la maggior parte del suo territorio fu incorporato in quello della diocesi di Carcassonne, mentre una porzione più piccola entrò a far parte della diocesi di Montpellier.
Nel giugno 1817 fra Santa Sede e governo francese fu stipulato un nuovo concordato, cui fece seguito il 27 luglio la bolla Commissa divinitus, con la quale il papa restaurava la sede metropolitana di Narbona. Tuttavia, poiché il concordato non entrò in vigore in quanto non ratificato dal Parlamento di Parigi, questa erezione non ebbe effetto. L'arcidiocesi non venne mai più restaurata. Dal 1822 gli arcivescovi di Tolosa ebbero il privilegio di aggiungere al proprio titolo quello di arcivescovi di Narbona.
La diocesi di Carcassonne fu eretta dopo il 533 ad opera dei Visigoti, che in questo modo cercarono di compensare la perdita di Lodève e Uzès, passate ai Franchi. Il suo territorio fu ricavato da quello dell'arcidiocesi di Narbona, di cui Carcassonne divenne suffraganea. Il primo vescovo di cui si abbia riscontro storico è Sergio che nel 589 prese parte ai concili di Toledo e di Narbona.
Nel IX secolo furono erette le chiese di Notre-Dame de Canabès e di Notre-Dame de Limoux, ancor oggi meta di pellegrinaggio. Alla fine dell'XI secolo fu ricostruita a Carcassonne la chiesa dei santi Nazaro e Celso e papa Urbano II, venuto a Carcassonne a predicare la crociata, benedisse l'inizio dei lavori. Le navate della chiesa sono di stile romanico, mentre il transetto e il coro sono gotici. Questa chiesa fu cattedrale della diocesi fino agli inizi dell'Ottocento; il capitolo seguì per lungo tempo la regola di sant'Agostino, ma nel 1439 fu secolarizzato.
La storia della diocesi nel XIII secolo si interseca con la vicenda degli albigesi e la stessa città di Carcassonne si trovò al centro della crociata albigese. Il monastero di Prouille, nel quale san Domenico nel 1206 fondò un istituto religioso per le albigesi convertite, è oggi una meta di pellegrinaggio, consacrata alla Vergine. San Pietro di Castelnau, l'inquisitorecistercense martirizzato dagli albigesi nel 1208; santa Camelia, condannata a morte dagli stessi eretici; e il gesuita san Giovanni Francesco Régis (1597-1640) nato a Fontcouverte nell'antica arcidiocesi di Narbona, sono i santi specialmente venerati nella diocesi di Carcassonne.
Il 6 ottobre 1822 con la bolla Paternae caritatis del medesimo papa Pio VII fu ristabilita la diocesi di Perpignano, recuperandone il territorio da quello della diocesi di Carcassonne.
^Non esiste documentazione storica circa questo vescovo, se non la menzione nella vita di un santo abate spagnolo, Vittorino, di scarso valore storico secondo Duchesne.
^Una lettera di un papa Stefano indirizzata a Aribertus archiepiscopus Narbonae è pubblicata dal Migne tra le epistole di papa Stefano VI (896-897). Ma all'epoca di questo papa era arcivescovo Arnusto; lo stesso discorso vale per i papi Stefano V e Stefano IV. Per cui il vescovo Ariberto è stato anticipato all'epoca di papa Stefano III, dopo il 7 agosto 768, giorno in cui il papa venne consacrato, e prima del 12 aprile 769, giorno in cui la storia documenta il successivo arcivescovo Daniele. Duchesne lo esclude dalla sua cronotassi, come pure Jacques Michaud e André Cabanis nella recente Histoire de Narbonne (1981).
^In competizione con Gerardo, ottenne dal papa il pallio nel 914, facendosi riconoscere come unico arcivescovo.
^Vescovo di Rodez, occupò in modo illegittimo la sede e per questo fu scomunicato da papa Gregorio VII nel 1080; solo nel 1086 rinunciò alla sede per ritornare a Rodez.
^La prima data è menzionata dall'Histoire générale de Languedoc; la seconda da Gams.
^Nominato dal capitolo della cattedrale, si trovò in competizione con François Hallé, nominato dal re e confermato dalla Santa Sede; solo nel 1484 accettò il trasferimento a Montauban.
^Secondo Eubel, Georges d'Amboise è nominato a Narbona il 2 dicembre 1491, ma questa data è incompatibile con quella di morte di François Hallé; forse si tratta di un refuso per 1492. Secondo l'Histoire générale de Languedoc (p. 256), d'Amboise ha fatto il suo ingresso solenne il 30 dicembre 1492.
^Contravvenendo alle disposizioni di papa Pio VII contenute nella bolla Qui Christi Domini, monsignor de Dillon non diede le dimissioni dalla sede di Narbonne e morì in esilio a Londra nel 1806.
^Riportato da Gallia christiana ma con la semplice indicazione: tradunt (ossia: è tradizione che ...). Secondo Duchesne, non esiste documentazione storica su questo presunto vescovo.
^Dopo Seniore, Gallia christiana menziona un vescovo di nome Liviula, il cui nome fu trovato nel 1607 in uno scritto contenuto nella cassa di san Lupino, morto nell'851. Secondo Duchesne e l'Histoire générale de Languedoc il documento è un apocrifo.
^Secondo Duchesne, le prove addotte da Gallia christiana sono scarse per ammettere con certezza Arnolfo tra i vescovi di Carcassonne.
^Ammesso da Gallia christiana e l'Histoire générale de Languedoc, è escluso da Gams. Gli autori dell'Histoire de Languedoc escludono il successivo Arnauld, perché non è provato che sia succeduto a Pierre.
^Menzionato per l'ultima volta agli inizi di agosto del 1007. Secondo l'Histoire de Languedoc, Guillaume Bernard sarebbe morto il 10 aprile 1008; Gallia christiana invece riporta come data di morte il IV idus Augusti, che potrebbe essere quello del 1007 o del 1008.
^Il 24 luglio 1409 è nominato patriarca di Alessandria; mantiene in amministrazione la sede di Carcassonne.
^Contravvenendo alle disposizioni di papa Pio VII contenute nella bolla Qui Christi Domini, monsignor de Vintimille non diede le dimissioni dalla sede di Carcassonne - pur autorizzando l'attività del successore imposto dalla Chiesa - e morì a Parigi nel 1822.