Il relie le choeur fortifié de la cathédrale au palais des archevêques. Il occupe l'emplacement de l'église carolingienne de Théodard, dont le clocher est toujours visible.

Les travaux, relayant ceux de la cathédrale, commencent en 1349 par la galerie Nord et se poursuivent par les galeries Est et Ouest. Après une interruption, ils sont repris en 1417, avec l'édification de la galerie et de la porte Sud.

Le cloître comporte 4 galeries voûtées d'ogives, éclairées chacune par 5 arcades en arc brisé.
A l'Ouest, le mur extérieur du cloître est contreforté. Autrefois fortifié, il présente encore quelques mâchicoulis.
A l'Est, la galerie communique avec la salle capitulaire, devenue chapelle de l'annonciade.

Les galeries du cloître qui servaient de cimetiere sont restées inachevées : absence de balustrade, de pinacles sur les deux côtés et de remplages aux arcades.

De la cathédrale de Narbonne, bâtie sur le modèle des grands édifices du gothique rayonnant du Nord de la France, seul le choeur est complètement terminé.
La première pierre est posée le 3 Avril 1272, sous l'épiscopat de l'archevêque Maurin. Les travaux effectifs commencent sous l'épiscopat de Pierre de Montbrun.(1272-1286)

A la fin du XIIIème siècle, toutes les chapelles sont édifiées. Le choeur est achevé et voûté avant 1332, année de sa prise de possession par les chanoines. Parallèlement, le transept et le début de la nef sont ébauchés. Les tours-clochers, élevées au cours du XIVème siècle, seront restaurées au début du siècle suivant.

Le choeur imposant à 4 travées mesure hors oeuvre 55 mètres de long sur 48 de large. Il comporte un vaisseau central, hissant ses voûtes d'ogives à plus de 45 mètres, flanquées de collatéraux et de deux séries de 4 chapelles pentagonales moitié moins élevées.

Il est prolongé par un déambulatoire desservant 5 chapelles rayonnantes de même plan mais plus amples que celles des bas-côtés.

A l'intérieur, le tombeau des archevêques, le retable polychrome et la vierge du XIVème siècle, le maître-autel à baldaquin du XVIIème siècle.

D'après la tradition, la vierge du pont de sainte Catherine se trouvait en grande vénération dans l'église de Lamourguier. Cette vierge miraculeuse avait remplacé une antique statue de Marie. Elle fut toujours un refuge de la ville en temps de calamités.
En 1525, les fortifications furent reconstruites. A cette époque, sur le pont que l'on appelait indifféremment le pont de Notre-Dame, la Cadène (en raison de la grosse chaine en fer que l'on tendait le soir d'une rive à l'autre pour empêcher la circulation des barques) ou bien de Sainte-Catherine, on édifia au milieu du pont une chapelle votive et l'on y plaça la statue vénérée.
Pendant 3 siècles, la statue fut vénérée. Elle était si aimée, que pendant la révolution elle fut respectée, et lorqu'en 1889 eut lieu le déclassement des fortifications comportant la démolition du pont, une vaste pétition demanda et obtint du gouvernement que l'on conservât le pont et la chapelle. Malheureusement, quand l'ordre arriva de Paris, la mine avait déjà fait son oeuvre et le pont était à moitié détruit.

Les Narbonnais firent alors placer la statue dans la cathédrale, où le pélerinage un instant interrompu a repris son cours. Lors de restaurations, on retrouva la fresque murale qui est autour d'elle. Sous ses pieds, à l'image de la vouivre, le "Léviathan".

Faisant suite au choeur gothique de la cathédrale, elle correspond au transept de l'église. Elle est délimitée à l'Ouest par l'amorce de la nef qui devait à l'origine comporter 5 chapelles pentagonales de chaque côté et dont deux seulement ont été élevées. L'édifice achevé aurait avoisiné les 120 mètres de longueur.

Vers 1340 sont réalisées les parties basses du bras Nord du transept, décelables à la teinte plus claire de la pierre. La poursuite des travaux exige que l'on détruise une section de l'enceinte fortifiée d'origine antique. les consuls s'y opposant, il s'ensuit un long procès.

Puis surviennent la peste noire de 1348 et le raid dévastateur du prince noir suivi d'un déclin économique sévère, lié notamment à l'ensablement du port. Le chantier est alors arrêté. Il est relayé par la construction du cloître et l'extension du palais attenant.
En 1840, Viollet-le-Duc y travaillera brièvement, ébauchant un pont fortifié, avant que le chantier ne soit définitivement abandonné.

Elle est devenue la chapelle de l'annonciade, réservée au culte. Au-dessus, désignée dans les textes du XVème siècle sous les termes de "capitulum novum" ou "capitulum rotodum", se trouve la salle de l'écho ou salle acoustique.

La coupole ellipsoïdale en briques lui confère une particularité remarquable. Une personne située dans un angle, face au mur, peut communiquer à voix basse distinctement avec son interlocuteur placé dans l'angle opposé, sans être entendue dans le reste de la pièce.

C'est dans cette salle que se trouve le trésor de la cathédrale, l'un des 10 plus riches de France.

Cette église est bâtie sur le tombeau du premier évêque de Narbonne, saint Paul, mort en 240. Une ancienne tradition identifie ce premier évêque à Paulus Sergius, proconsul de Chypre converti par l'apôtre Paul. Grégoire de Tours fait de Paul un compagnon des évangélistes Trophime d'Arles, Saturnin de Toulouse et Aphrodise de Béziers. Cette fondation de l'église de Narbonne se situe donc au début du IIIème siècle.

Sur le tombeau de saint Paul proche des voies Domitienne et d'Aquitaine, se sont succédés plusieurs édifices depuis un oratoire primitif (aux environs de 250) auquel succèdera divers édifices de plus en plus importants, pour aboutir à l'église actuelle.

Ainsi, une petite basilique (12m x 6m50) érigée en 313 fut détruite par le feu au Vème siècle, un monastère fondé en 782 fut ruiné à son tour. Le tombeau préservé de Saint Paul deviendra lieu de pélerinage et de dévotion, d'autant plus avec le développement du pèlerinage vers Compostelle, et la situation de Narbonne sur la voie du piémont Pyrénéen. Les chansons de geste attestent la célébrité de la basilique carolingienne.

Autour du sanctuaire agrandi se développera, hors murailles antiques et se protégeant à son tour par un rempart, le Bourg Saint-Paul. Comme la cité, il aura ses propres consuls, et le consulat y siègera toujours.

Au XIIème siècle, dans la prospérité retrouvée, un beau monument sera édifié. Le choeur incendié sera reconstruit entre 1224 et 1230, et les voûtes refaites en 1368.  Le tombeau de Paul Serge  fut placé en 1244 au rond-point du nouveau chœur et fut transféré en 1265 au pied des colonnes du maître-autel, où une chasse contint les reliques jusqu'à la révolution.
Au XVème siècle, deux travées supplémentaires sont bâties, et au XVIème siècle, on consolide plusieurs piliers et on rajoute 3 arcs. Saint-Paul-Serge, l’une des plus anciennes églises gothiques du midi de la France, est considéré comme un sommet de l’art gothique primitif. 

L’ensemble apparaît typiquement méridional. Maintenant qu’il vient d’être dégagé, nous pouvons apprécier l’élégance discrète du chevet. Cette construction de structure ogivale ne ressemble en rien aux édifices contemporains du nord de le France : aucun arc boutant, le mur épais est soutenu par des contreforts, les étroites fenêtres des chapelles sont encadrées de fines colonnes engagées aux chapiteaux ornés de crochets, feuillages et monstres.

Le clocher du XVIème siècle est une énorme tour de 40 m de haut que la suspension en ferronnerie des cloches domine de dix mètres.
L'ancienne entrée, sur la façade Ouest, a été murée lors de la construction des remparts au XVIème siècle.

Plusieurs fois remaniée, cette ancienne collégiale demeure le premier témoignage à Narbonne du nouveau style qui s’empare des églises françaises au XIIIème siècle : le gothique. Dès 1180-1200, la nef qui sera allongée de deux travées à la fin du XIVème siècle, subit d’importants travaux faisant de Saint-Paul l’une des plus anciennes églises gothiques du midi de la France.

En 1224, c’est au tour du chœur d’adopter les nouvelles formules du gothique : une élévation à trois niveaux composée de grandes arcades, d’un double triforium éclairé (galerie ajourée ménageant des jeux de lumière) et de fenêtres hautes, un déambulatoire à voûtes, cinq chapelles absidiales. Le maître-autel en baldaquin du XVIIIème siècle a une chasse d'apparat qui contenait jusqu'à la révolution le corps présumé de Saint-Paul.

La voûte d’ogives, qui culmine à 22 m, domine un déambulatoire haut desservant des chapelles rayonnantes à sept pans. La longueur totale est de 82 m. Les contreforts soutenant habituellement les voûtes d’ogives dans l’art gothique sont remplacés ici par le mur enserrant l’ensemble des chapelles du chevet. L’aspect ondulé si particulier de ce chevet à couverture unique est renforcé par de fines arcatures aveugles.

De l’époque romane subsistent les trois premières travées de la nef.

L’orgue de chœur de la basilique, signé Baptiste Puget et datant probablement des années 1880, a été restauré en 2006 et inauguré lors du festival européen Musique et Orgue en Pays narbonnais.

Dans la nef, des piliers cruciformes à colonnes engagées, spécimens de l’art primitif d’Ile de France, uniques dans le midi, la curieuse galerie, témoins d’âges divers, qui court autour de l’église, le triforium réputé par ses baies à claire-voie ajourées sur l’extérieur (aujourd’hui aveugles) qui annonce les belles galeries gothiques.

Au fond de l’église, la sculpture de Jésus au puits de la samaritaine (sur un sarcophage de l’époque romaine, IVème siècle)

Dans la seule travée subsistant du cloître roman, une cuve archaïque de sarcophage, un tympan décoré d’un bas relief où huit abbés mitrés entourent deux évêques. On peut voir dans le plus grand de ces personnages, le saint évêque Paul. L’inspiration byzantine de ce bas-relief permet en effet de penser que la taille du personnage est le symbole de sa grande sainteté.

Au fond de l’église, de part et d’autre des fonts baptismaux qui occupent l’ancien narthex de l’église, sont visibles des sarcophages paléochrétiens.

La grenouille du bénitier

L'un des piliers supporte le fameux bénitier à grenouille, de forme jacquaire, dont la légende veut que fut pétrifié là un animal qui avait troublé l’office. Se rattache à cette sculpture le conte d’un jeune compagnon tailleur de pierre, contraint par son père de revenir à Narbonne parce qu’il avait oublié de l’admirer dans son tour de France. Il se vengea en cassant une des pattes de la grenouille.
Une autre légende raconte que saint Paul, venant de Rome, aborda à Bages. Il y fut mal reçu par les habitants qui, pour se moquer de lui, l’obligèrent à rouler un rocher et à monter sur ce rocher pour traverser l’étang. Il faisait un vent de tempête et d’énormes vagues menaçaient d’engloutir le rocher et le saint évêque. Mais saint Paul, plein de foi, monte sur le rocher qui se transforme en nacelle. C’est alors qu’une grenouille sauta dans l’embarcation et conduisit saint Paul sur le rivage de la Nautique. De là, il atteignit la ville de Narbonne. Le bénitier avec la grenouille providentielle rappellerait la miraculeuse nacelle qui amena saint Paul dans la ville qu’il allait évangéliser.

Alors que le christinanisme devient la religion officielle de l’empire romain, les premiers bâtiments cultuels sont construits. L’ancien cimetière paléochrétien (IIIème-IVème siècles) est appelé communément la "crypte" par les Narbonnais.
Aménagée autour de colonnes romaines en réemploi, cette "cella memoriae" remise à jour en 1946, se divise en salle de sarcophages et salle de banquets funéraires.

Le sol, décoré de mosaïques des IIème et IIIème siècles fut cassé pour y descendre six sarcophages (cinq en marbre, un en pierre) du IIIème et Vème siècles,  illustrant différents courants artistiques de l’art funéraire.

Le plus célèbre, dit de l’école d’Arles, retaillé dans un marbre antique,  est le mausolée d’une riche famille romaine, dont les défunts sont représentés sur le couvercle de part et d’autre d’un cartouche et encadrés par la Lune (Isis-Séléné) et le Soleil (Sérapis-Hélios).

Une des faces de la cuve porte des strigiles caractéristiques. Ces cannelures en forme de S cernent une Victoire gravant sur un bouclier une inscription énigmatique :  Lege Feliciter, lis heureusement. C'est à dire, comme au Puy, "regarde bien..."
C’est probablement l'un des plus anciens témoins de la Gaule chrétienne.

La crypte abrite également des amphores contenant des ossements d’enfants, une pratique très courante dans l’Antiquité tardive pour les plus jeunes d’entre eux (jusqu’à 4-5 ans).

La présence d'habitants nomades à Béziers est attestée par la découverte d'outils primitifs (atelier de silex de la période magdalénienne) datant de -12 000.  La boucle de l’Orb, au pied de la colline Saint-Nazaire, est occupée de manière sédentaire depuis l'ère néolithique. Durant l'âge du fer (VIIIème‑IIème siècle avant notre ère), Béziers constitue l'un des principaux oppida de la Celtique méditerranéenne.

Les premiers témoignages historiques datent de la fondation de la ville, par les Grecs, au VIème siècle avant notre ère (Betara, plus de 40 hectares).
Les relations commerciales furent très vites privilégiées avec les Grecs d'Europe et d'Asie, les Etrusques et les Phéniciens grâce à la proximité du rivage. Sous zone d'influence ibérique, l'oppidum de Béziers, etait très riche grâce au commerce et à la plaine fertile qu'elle dominait.

Les Romains chassent les Celtibères dès le Ier siècle avant notre ère pour s'y installer et y créer une colonie, la Civitas urbs baeterrensis. Située à quelques kilomètres de la mer Méditerranée sur le fleuve Orb, traversée par la Via Domitia qui relie l'Italie à l'Espagne, Baeterrae, nom antique de Béziers, prospère jusqu'au IIIème siècle avant notre ère où l'insécurité ambiante amène la cité à construire des murailles. On y développait alors la culture de la vigne et de l’olivier, on défrichait les forêts de chênes environnantes.

Les invasions barbares touchent de plein fouet Béziers, au centre d'une Narbonnaise très disputée : d'abord aux mains des Wisigoths au VIème siècle, elle est bientôt conquise par les musulmans au début du VIIIème siècle siècle, puis par les Francs qui, menés par Charles Martel la ruinent en 737. Siège d'un évêché puis bientôt, grâce à Charlemagne, d'un comté, Béziers continue à se fortifier, notamment au début du XIIème siècle, au moment de la grande guerre méridionale entre la maison d'Aragon et la maison de Toulouse, et son enceinte, englobant les bourgs de Capnau, Saint-Aphrodise et Saint-Jacques, prend sa forme définitive.

En 1209, le 22 juillet, le vicomte de Béziers, Raimond-Roger Trencavel, ne peut résister aux assauts des croisés du Nord, menés par Simon de Montfort, venus châtier les hérétiques Albigeois : tous les habitants de Béziers sont passés par les armes au cours d'un des plus grands massacres du Moyen Âge. Césaire de Heisterbach, moine cistercien vivant près de Bonn, a rapporté la célèbre phrase que le légat du pape Innocent III, l'abbé Arnault, aurait proclamée : "Tuez-les tous, Dieu reconnaîtra le siens". En fait la phrase originelle serait  "Massacrez-les, car le seigneur connaît les siens". On a baptisé ce jour "Lo gran mazel", la grande boucherie.

La cathédrale de Béziers est reconstruite, Béziers intégrée au domaine royal en 1247. gagnée par les pratiques nouvelles qu’Aliénor d’Aquitaine, future reine de France puis d’Angleterre et mère de Richard Cœur de Lion, avait imposées en son duché, Béziers épousa les "cours d’amours" et la cause des troubadours. Ils ont nom Guilhem Augier, Ramoun Gaucelm, Matfre Ermengaud. Cet essor culturel ne résiste pas aux affres du XIVème siècle.

A partir du XVème siècle, la paix revint et Béziers développa un nouvel art de vivre grâce à une économie plus que favorable. L'évêché connaît son apogée au XVIème et au XVIIème siècle quand il est occupé par la famille des Bonsi, alliée aux Médicis. Néanmoins, la révolte de Montmorency en 1632 valut une sévère répression de la part de Richelieu. L'image de Béziers se trouva restaurée lorsque l'illustre Pierre Paul Riquet, enfant de Béziers, décida de construire à ses propres frais en 1667 le Canal du Midi, reliant l'Atlantique et la Méditerranée, qui sera inauguré en 1681 après sa mort. Le XIXème siècle est surtout marqué à Béziers par la viticulture. Cette activité entraina une spectaculaire augmentation de la population grâce à l'arrivée de main d'oeuvre. Son blason, d'argent à trois fasces de gueules au chef d'azur chargé de trois fleurs de lys d'or.