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.
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.
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.
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.
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.