Dos autores antiguos nos hablan de san Pablo de Narbona: Prudencio, que vivió en el siglo IV, en su poema Peristephanon (De las coronas de los mártires), y san Gregorio de Tours, del siglo VI, en su Historia Francorum (Historia de los Francos). Prudencio hace un repaso de los santos que dieron brillo a algunas ciudades (Barcelona, Calahorra, etc.) y entre ellas incluye el de Pablo como lustre de la ciudad de Narbona. Pero puesto que el Peristephanon trata acerca de mártires, sería un testimonio de que Pablo de Narbona murió por la fe; aunque cabe aclarar que Prudencio no dice explícitamente que fue mártir, sino que su obra trata de ello. La tradición iconográfica lo ha vestido de rojo, como a un mártir, aunque el Martirologio Hieronimyanum lo inscribe como «confesor», lo que solía indicar que sufrió por la fe sin llegar a ser mártir.
Gregorio de Tours cuenta algo más: por lo pronto es clara la época en que se ubica el santo, mediados del siglo III, y pertenecería a un grupo de siete varones ilustres que fue enviado desde Roma para evangelizar la Galia. Es, por tanto, obispo misionero, y el primero de la sede de Narbona. Los demás fueron, los mártires y fundadores san Saturnino de Toulouse y san Dionisio de París, y los también fundadores de sedes galas, san Trófimo de Arles, san Marcial de Limoges, san Gaciano de Tours y San Austremonio de Auvernia.
Con el paso de los siglos, las sedes episcopales, que eran también entidades políticas, competían entre sí por la primacía en la región. Uno de los puntos en esta competencia era quién podía presentar un origen más antiguo o ilustre: si había sido evangelizada por un apóstol de Jesús, si por un discípulo mencionado en los evangelios o en los Hechos, etc. En muchos casos se forzaban las identificaciones para llevar uno o dos siglos más atrás la fundación: para los historiadores de los siglos IX y X, el siglo III, que fue la gran evangelización de la Galia, parecía demasiado cercano, demasiado tardío para fundamentar las expectativas del obispo del lugar. Surgen así en esos siglos las leyendas que identifican a uno u otro fundador con uno u otro personaje prominente del NT. En muchos casos se apela a identificar al primer obispo de la sede con uno de los 72 anónimos discípulos enviados por Jesús, en otros, como en el caso de san Pablo de Narbona, se encuentra en el NT un personaje mencionado con su nombre, candidato, por tanto, a darle al obispo de Narbona el prestigio de la antiguedad. Se trata del procónsul Pablo-Sergio, del que Hech 13,7 dice que era un hombre prudente, y que llamó a Pablo y Bernabé, deseoso de escuchar la palabra de Dios.
La legendaria identificación entre Paulo-Sergio y san Pablo de Narbona parece que se la debemos al hagiógrafo Adón, del siglo IX; al menos es en su martirologio donde por primera vez aparece. Inventada pero de gran éxito: aun hasta hoy, aunque ya se ha reconocido desde hace siglos que no hay ninguna razón para considerar que san Pablo de Narbona es anterior al siglo III, en el culto narbonense se le sigue llamando Saint Paul-Serge.
La fecha del 22 de marzo surge de la inscripción en el Martirologio Hieronymianum. En la colegiata de San Pablo, en Narbona, se excavó un cementerio de las primeras épocas del cristianismo en la ciudad, que es muy probable que contenga la tumba del santo. Hay una «Actas» de san Pablo que pretenden narrar hechos de su vida, pero son tardías, y traen más confusión que soluciones.
Ver Duchesne, Fastes Episcopaux, I, pág. 302-3; Acta Sanctorum, marzo III, pág. 371ss. reproduce toda la docuemntación, incluyendo las actas legendarias; Prudencio, Peristephanon IV, estrofa 9; Gregorio de Tours, Hist. Franc. I,30. Vale la pena la interesante galería iconográfica de la Colegiata de San Pablo, con un resumen (en francés) de las tradiciones narbonenses acerca de san Pablo (St. Paul-Serge).