Paul of Narbonne (3rd century CE) was one of the "apostles to the Gauls". They had been sent out (probably by Pope Fabian, 236–250) during the consulate of Decius and Gratus (250-251 AD). Their mission was to Christianise 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: Paul to Narbonne, Gatien to Tours, Trophimus to Arles, Saturnin to Toulouse, Denis to Paris, Austromoine to Clermont, and Martial to Limoges.

Very little about Paul has survived to the present day. That he was among those priests consecrated at Rome and sent to replant the Christian communities in Gaul was affirmed by Gregory of Tours (Historia Francorum I, 30), who was reading the acta of Saturnin. He and Denis had been martyred, but Paul survived to establish the church at Narbonne as its first bishop, and to die of natural causes around 250.

It was in a pagan necropolis, somewhere along the Domitian Way, that Paul was buried. His tomb, the object of substantial veneration and around which were various sanctuaries^[2], was to be the focus of the first Christian cemetery in Narbonne.

Prudentius' claim that Paul brought fame to Narbonne may be hyperbole. Edited by the Bollandists is a brief Vita Antiqua, perhaps of the 6th century. It suggests 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 suggests two acolytes placed a lady's slippers at the foot of his bed, telling of improprieties, but that this was both confounded and forgiven by Paul miraculously.

Earliest surviving mention of Paul is in a 5th century text, in which his evangelizing and protection of the people of Narbonne drew comparison with that of Cucufas in Barcelona. In the 7th century, the bishop of Arles, Saint Caesarius, in his treatise De mysterio Sanctae Trinitatis also refers to Paul. Another reference to him is in the 7th century Historia Francorum written by Gregory of Tours.

Mis-identification with Sergius Paulus

It is largely thanks to Jean de Launoy, in 1650, that Paul's hagiography was lent historiographic respectability. Medieval legends appeared to have moved the seven apostles of Gaul back in time to the apostolic generation (see especially Martial of Limoges), perhaps in order to bolster local traditions with apostolic connections. One such legend identified the third-century Paul with the Roman proconsul Sergius Paulus, converted two centuries earlier by Paul the Apostle (Acts 13:6–13). In Narbonne itself Saint Paul-Serge is still conflated with the historical Paul of Narbonne.

It was also mere fancy that Paul accompanied Aphrodisius, later first bishop of Béziers. That this was he who might have sheltered the Holy Family during their flight into Egypt was another medieval fabrication^[3].

St Paul Basilica

At Narbonne the basilica of Saint Paul, built over Paul's grave and Narbonne's first church, is a collegiate church^[4]. After Paul's death, the city was smaller than it had been. A city wall surrounded an area of barely a third of a sq km (0.14 sq mi). The current building, dating from the 13th century, is one of the oldest in southern France.

The early shrine was small, 12 metres by 6.5 metres, built in the 4th century. The basilica became the centre 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. The Visigoths captured Narbonne in 462, but this may possibly have not threatened the building. In the 5th century it was destroyed by fire, and was then the site of a monastery.

In 719, Narbonne was conquered by Muslim armies. A mosque was installed in part of the atrium of the basilica. It was then destroyed without trace after the Merovingian reconquest of 759.

Documents from 782 and 843, found among the archives, indicate a community of clerics serving at the church. The text of 782 shows that the church of Saint Paul was recognised as an ecclesia, i.e. the most important church after the cathedral.

The basilica was rebuilt more than once, most recently between 1180^[5] and 1200, during a period of renewed urban prosperity, reusing old materials and always retaining its ancient foundations. The style is Gothic, but it was not until 1224-1230, after a fire, that the area where the choir sat was built. The basilica became one of the major pilgrimage stops on the Via Tolosana (between Rome and Compostela) throughout the Middle Ages.

Excavations 1942-1946^[6] brought to light a paleo-Christian cemetery (2nd-3rd century) under the current church's apse, i.e. the semicircular east end, where the choir sat. In the basilica's crypt mosaic flooring can be seen. Unearthed beneath the north side of the church are the foundations of a pre-Christian chamber for six sarcophagi, aligned side by side. This is thought to have been a cella memoriae, i.e. a small construction over a grave where a feast might honour an anniversary.

"Saint Paul's frog", in the veinings of a marble stoup, has given rise to fanciful anecdotes.