Le diocèse actuel tire son origine de l'ancien diocèse de Paestum(it) ; La première preuve historique de l'existence d'un évêque pour ce site remonte aux synodes romains organisés par le pape Symmaque en 499 et en 501, auxquels l'évêque Fiorenzo prend part. Parmi les évêques présents au concile de Latran convoqué en 649 par le pape Martin Ier, se trouve l'évêque Giovanni de Paestum. Après le VIIIe siècle, le diocèse de Sala Consilina(it), dont on connaît trois évêques, et le diocèse de Velia(it), mentionné dans les lettres de Grégoire Ier, sont probablement unit au diocèse de Paestum. De l’ancien diocèse, il reste la cathédrale, maintenant déconsacrée et récemment restaurée, dédiée à l'assomption, qui existe déjà à l’époque du pape Grégoire le Grand, mais qui est abandonnée par la suite. En fait, la ville de Paestum, en raison de l'insalubrité de l'environnement puis des raids sarrasins du IXe siècle, est progressivement abandonnée et ses habitants se réfugient dans les montagnes voisines, donnant ainsi naissance à la ville de Caput Aquae, laquelle a probablement donné le toponyme de Capaccio.
Les évêques déménagent également à Capaccio, bien que la période exacte du transfert de la résidence de l'évêque ne soit pas connue, cela semble néanmoins se situer au cours du Xe siècle. Ils continuent pourtant à être appelés évêques de Paestum jusqu'au environ de la moitié du XIIe siècle ; Les premiers à s'appeler episcopi Caputaquensis sont Alfano en 1126, Celsus en 1156 et Leonardo en 1159. Le diocèse est très vaste et comprend presque tout le Cilento et le Valdiano(it). Cela rend difficile, voire impossible, une organisation ecclésiastique efficace du territoire, et la présence chrétienne est surtout garantie grâce au monastères grecs-byzantins puis aux bénédictins. Le diocèse faisait alors partie de la province ecclésiastique de l'archidiocèse de Salerne.
L'évêque Enrico Loffredo (1531-1547) prend part au concile de Trente, et se distingue par sa ferme position en faveur des réformes. Il est parmi les victimes du typhus qui se propage à Trente en 1547. Le premier séminaire épiscopal est établi le à Teggiano par l'évêque Paolo Emilio Verallo (1553-1574) et fut l'un des premiers séminaires mis en place après les dispositions tridentines. Un deuxième séminaire est érigé à Novi en 1804 par Filippo Speranza. Mgr Verallo convoque le premier synode diocésain, célébré à Padula en 1567. Après le concile de Trente, le , la résidence de l'évêque est transférée à Diano, où l'église de Sainte Marie Majeure est érigée en cathédrale ; le diocèse conserve toutefois l'ancien titre de Capaccio. Plus tard, les évêques déménagent encore à Sala Consilina (1627), à Pisciotta, à Capaccio Nuova et enfin à Novi Velia (1845): ces transferts continus indiquent clairement que le diocèse n'avait ni un siège stable ni une unique cathédrale.
En raison de l'immensité du territoire et pour remédier aux difficultés rencontrées par les évêques sans siège fixe, le , le pape Pie IX décrète l'érection du diocèse de Diano (aujourd'hui diocèse de Teggiano-Policastro), attribuant au nouveau diocèse la partie orientale du diocèse de Capaccio. En même temps, l'abbaye territoriale de Bosco à San Giovanni a Piro est supprimée et ses territoires sont annexés au diocèse de Capaccio. L'année suivante, le , par la bulleCum propter iustitiae dilectionem, le même pape établit définitivement la résidence épiscopale des évêques de Capaccio à Vallo della Lucania, où l'église de San Pantaleone devient la nouvelle cathédrale, qui est consacrée le ; en même temps, le siège prend le nom de diocèse de Capaccio et Vallo (Caputaquensis et Vallensis). Une période difficile pour le diocèse coïncide avec l'épiscopat de Giovanni Francesco Siciliani (1859-1876), contraint à l'exil pendant environ dix ans, tandis que le diocèse subit la confiscation des biens ecclésiastiques prévue par les lois subversives de 1866 et 1867.
Le séminaire épiscopal de Teggiano se trouvait alors en dehors des frontières diocésaines ; le , l'évêque Siciliani pose la première pierre d'un nouveau séminaire à Novi Velia. En 1930, un nouveau séminaire à Vallo est inauguré par l'évêque Francesco Cammarota; le même évêque célèbre un synode diocésain en 1921. L'évêque Paolo Jacuzio (1900-1917) donne une impulsion décisive à la propagation de l'action catholique. Le , le diocèse change de nom pour devenir le diocèse de Vallo di Lucania. Le , il prend le nom actuel. Le , Mgr Giuseppe Casale fonde le musée diocésain et la pinacothèque afin de préserver et d'accroître le patrimoine historique et artistique du diocèse, en le plaçant au premier étage du séminaire. Dans le même bâtiment, se trouve le siège de l'institut supérieur des sciences religieuses pour la formation théologique, biblique et spirituelle des laïcs et les archives diocésaines. Le , le diocèse élargit son territoire en annexant 15 paroisses qui dépendaient jusque-là des abbés de la Sainte-Trinité de Cava de 'Tirreni.