Paul Naudo nait aux Angles en 1794. Il est issu d'une famille ayant appartenu à la noblesse d'Espagne, mais devenue modeste. Il commence ses études auprès d'un de ses oncles ecclésiastique de l'ancien régime et les poursuit à Carcassonne où il entre au Grand-Séminaire. Ordonné prêtre en 1818 il devient en 1820 chanoine honoraire de la cathédrale Saint-Michel de Carcassonne et il enseigne pendant six ans (1818-1824) la philosophie et la théologie dans les diocèses de Carcassonne et de Perpignan.
Aux termes du concordat de 1817, le diocèse de Perpignan redevient, indépendant en 1823 de l'évêché de Carcassonne. Le nouveau évêque Jean-François de Saunhac-Belcastel nomme l'abbé Naudo, à peine âgé de trente ans, à la tête de son nouveau Grand-Séminaire, qui s'implante provisoirement à Prades grâce à un accord conclu en 1825 entre la municipalité l'administration épiscopale. Toutefois dès le de l'année suivante, l'évêque bénit et pose la première pierre d'un Grand-Séminaire sur l'emplacement de l'ancien cimetière de l'église Cathédrale Saint-Jean-Baptiste de Perpignan. A Perpignan, Jean-François de Saunhac-Belcastel le nomme chanoine titulaire, grand-vicaire et en 1831vicaire-général. Après avoir refusé le siège épiscopal de Clermont-Ferrand en 1833, Paul Naudo obtient celui de Nevers, auquel le roi Louis-Philippe le nomme en 1834. Une bulle pontificale de Grégoire XVI, du , le confirme comme évêque de Nevers, en remplacement de Charles Douhet d'Auzers, mort le 9 février précédent. Il est consacré dans la capitale le 9 novembre suivant par l'archevêque de Paris, et prend possession de son siège à Nevers le . Louis-Philippe lui décerne la croix de la Légion d'honneur le et en 1837, il évite par son intervention à Clamecy, un affrontement entre l'armée et plusieurs centaines d'ouvriers.
En récompense de huit années d'activité intense dans le diocèse de Nevers, la nonciature et le gouvernement français s'accordent pour l'élever à la dignité archiépiscopale, sur le siège d'Avignon. Nommé le et préconisé le 22 juillet suivant, Paul Naudo arrive dans sa ville métropolitaine le de cette même année. La collection de ses mandements, lettres pastorales ou circulaires s'élève au chiffre de quarante-huit opuscules; dans ce nombre, vingt-cinq furent publiés à Nevers et vingt-trois à Avignon. Le jour de Pâques, , Paul Naudo, pendant la messe qu'il célébrait à Notre-Dame-des-Doms, son église métropolitaine, meurt d'une attaque d'apoplexie. Il est inhumé dans sa cathédrale.
Publications
Cantiques et goigs a N.D. de Font-Romeu Vaison: Imp. Bonne Presse du Midi, s.d.
Bréviare nivernais de l'office divin Nevers: Laurent typ., 1835
Lettre pastorale... à l'occasion de la retraite ecclésiastique qui doit s'ouvrir au Grand Séminaire Avignon: impr. Aubanel, 1843
Mandement... à l'occasion du tremblement de terre de la Guadeloupe Avignon: L. Aubanel, 1843
Mandement de... l'archevêque d'Avignon, à l'occasion de son entrée dans son diocèse Avignon: L. Aubanel, 1842
Mandement de Monseigneur l'évêque de Nevers à l'occasion de son entrée dans son diocèse Nevers: [s. n.], 1834
Mandement de Monseigneur l'Archevêque d'Avignon, à l'occasion des Religieuses de Saint-Joseph, de cette ville Paris-Avignon: Librairie Ecclésiastique de Seguin Ainé 1846 (fac-similé moderne de Kessinger Publishing, 2010, (ISBN9781160187107))
Mandement de Monseigneur l'évêque de Nevers, pour le Carême de 1835 Nevers: imp. I.C.Laurent, 1835
Mandement de Monseigneur l'Archevêque d'Avignon, pour le saint temps de Carême de 1843: sur l'immortalité de l'âme Avignon: Laurent Aubanel, 1843
Mandement de Monseigneur l'Archevêque d'Avignon, pour le saint temps de Carême de 1844: sur l'humilité Avignon: Laurent Aubanel, 1844
Mandement de Monseigneur l'Archevêque d'Avignon, pour le saint temps de Carême de 1845: sur l'œuvre de la propagation de la foi Avignon: Laurent Aubanel, 1845
Mandement de Monseigneur l'Archevêque d'Avignon, pour le saint temps de Carême de 1846 Avignon: Laurent Aubanel, 1846
Mandement de Monseigneur l'Archevêque d'Avignon, pour le saint temps de Carême de 1847 Avignon: Laurent Aubanel, 1847
Mandement... qui prescrit des prières en faveur de l'Eglise d'Espagne, avec indulgence plénière en forme de jubilé Avignon: impr. Aubanel, 1842
Armes
D'azur à l'ancre d'argent, au chef cousu de gueules de 3 croix de consécration ou antique d'argent[1].
Jean Capeille, « Naudo (Paul) », dans Dictionnaire de biographies roussillonnaises, Perpignan,
Jean Capeille, Figures d'évêques roussillonnais, Revue catalane n°3 (1909), p. 89-94
Paul Pisani, L'épiscopat français depuis le Concordat jusqu'à la Séparation (1802-1905) Société bibliographique (France). Librairie des Saints-Pères, 1907 - 720 p.
Abbé Voillot, Oraison funèbre de Mgr Naudo, archevêque d'Avignon, prononcée le , dans la Métropole, petit in-12, 48 p.