De eerste aanwijzingen van een christelijke aanwezigheid in het latere aartsbisdom Valencia gaan terug op het begin van de 3e eeuw. Toen Vincentius van Zaragoza op 22 januari304 de marteldood stierf in Valencia, bestond er al een plaatselijke christelijke gemeenschap. Het eigenlijke bisdom Valencia werd echter pas opgericht in 527, als suffragaan bisdom van het aartsbisdom Toledo.
Nadat koning Jacobus I van Aragón op 9 oktober1238 de stad heroverd had op de moslims, werd het bisdom opnieuw opgericht. De hoofdmoskee van Valencia werd hierbij omgewijd tot kathedraal en opgedragen aan de Moeder van Christus, en meer bepaald aan het mysterie van de Tenhemelopneming, waaraan de koning bijzonder toegewijd was. De aartsbisschop van Tarragona, Pedro de Albalat, voegde het nieuwe bisdom toe aan zijn kerkprovincie. Dit veroorzaakte echter een dispuut met aartsbisschop Rodrigo Jiménez de Rada van Toledo, een dispuut dat in het voordeel van Tarragona beslecht werd.[1]
In 2010 voerde Carlos Osoro een hervorming door van de decanaten en territoriale vicariaten, om ze aan de nieuwe bevolkingsaantallen en aan het nieuwe aantal priesters aan te passen. Hij streefde hiermee tevens een nieuw missionair dynamisme na.
