Den hellige Paul av Narbonne ble født i Roma tidlig på 200-tallet og presteviet der mot midten av århundret.
Den hellige Gregor av Tours forteller i sin «Frankernes historie» (Hist. Franc. I, 30) at under keiser Decius (249-51) ble syv misjonærer sendt fra Roma for å evangelisere Gallia. To av dem led martyrdøden, nemlig de hellige Saturnin av Toulouse og Dionysius av Paris, mens de hellige Trofimus av Arles, Gatian av Tours, Austremonius av Clermont-Ferrand, Martial av Limoges og Paul av Narbonne døde i fred etter liv av stor hellighet. Hver av disse helgenene misjonerte sitt eget distrikt, omvendte folket og var vitne til utbredelsen av troen. De etablerte et bispesete i hver region og bygde kirker ved sine respektive seter tross mange farer.
Paul ble biskop av Narbonne og Prudentius sier at Pauls tilknytning til byen hadde gjort den berømt. Der døde han ca år 290. Hans minnedag er 22. mars. Hans navn står i Martyrologium Romanum. Franskmennene elsker jo å kalle sitt land for «Kirkens eldste datter», og det oppsto tidlig behov for å pynte litt på historiene for å flytte kristningen av Frankrike til apostlenes tid. Mange av de tidligste franske helgenene ble utstyrt med biografier som flyttet dem flere århundrer frem i tid og identifiserte dem med skikkelser som var nevnt i Bibelen. En senere legende identifiserer Paul av Narbonne med den romerske prokonsulen Sergius Paulus, som ble omvendt av apostelen Paulus (Apgj 13).