Paul of Narbonne
Saint Paul of Narbonne (3rd century AD) was one of the "apostles to the Gauls" sent out (probably under the direction of Pope Fabian, 236–250) during the consulate of Decius and Gratus (250-251 AD) to Christianize Gaul after the persecutions under Emperor Decius had all but dissolved the small Christian communities. According to the hagiographies, Fabian sent out seven bishops from Rome to Gaul to preach the Gospel: Gatien to Tours, Trophimus to Arles, Paul to Narbonne, Saturnin to Toulouse, Denis to Paris, Austromoine to Clermont, and Martial to Limoges.

Gregory of Tours (Historia Francorum I, 30), using the acta of Saturninus, affirms that Paul was among those priests consecrated at Rome and sent to replant the Christian communities in Gaul.  Saturninus of Toulouse and Dionysius (Denis) of Paris were martyred, but Paul survived to establish the church at Narbonne as its first bishop and die in peace. The claim of Prudentius that Paul's association with the city of Narbonne had made it famous may be read as literary hyperbole. There is a brief Vita Antiqua  perhaps of the 6th century, which has been edited by the Bollandists. It tells that Paul converted the inhabitants of Béziers, setting over them a bishop, Aphrodisius, before turning his attention to Narbonne, where he founded two churches. An anecdote recounts how two of his acolytes set a woman's slippers at the foot of his bed, to accuse him of improprieties, but Paul was able miraculously to confound and pardon them.

Identification with Sergius Paulus
Medieval legends moved the seven apostles of Gaul back in time to the apostolic generation (see especially Martial of Limoges), in order to strengthen local traditions with apostolic connections; such a legend identified third-century Paul with the Roman proconsul Sergius Paulus, who was converted by Paul the Apostle (). The historical Paul is still venerated in Narbonne as Saint Paul-Serge through this connection.  He is said to have been accompanied by Aphrodisius, who later became the first bishop of Béziers and whom developing tradition identified as the man who sheltered the Holy Family during their flight into Egypt.

At Narbonne the basilica of Saint-Paul-Serge is a collegiate church built over the burial site of Paul, the first bishop. The site is at the border of an extensive necropolis of early Christian burials. The early shrine was a small basilica, 12 meters by 6.5 meters, built in the 4th century, destroyed by fire in the 5th century, then occupied by a monastery. As a place of pilgrimage first mentioned in 782 it was rebuilt more than once, most recently between 1180 and 1200, during a period of renewed urban prosperity, reusing old materials and always retaining its ancient foundations. After a fire, work on rebuilding the choir resumed from 1224. The paleochristian crypts survive, with 2nd-3rd century mosaic flooring and sarcophagi.

The basilica became the center of the Bourg Saint Paul sited somewhat apart from the Roman citadel of Narbonne, protected by its own walls and retaining its own separate consuls. "Saint Paul's frog", recognizable in the veinings of a marble stoup, has given rise to fanciful anecdotes.