The cathedral was consecrated in 1238 by the first bishop of Valencia after the Reconquista, Pere d'Albalat, Archbishop of Tarragona, and was dedicated to Saint Mary by order of James I the Conqueror.

[3] There is documentary evidence that some decades after the Christian conquest of the city (1238), the mosque-cathedral remained standing, even with the Koranic inscriptions on the walls, until 22 June 1262, when the then bishop Andreu d'Albalat [4] resolved to knock it down and build a new cathedral in its place according to the plans of the architect Arnau Vidal.

Some reasons for the simplicity and sobriety of Valencia Cathedral are that it was built quickly to mark the Christian territory against the Muslims, and that it was not a work by a king, but by the local bourgeoisie.

[7] Although there are several styles of construction, this cathedral is basically a Gothic building, a cruciform plan with transepts north and south, and a crossing covered by an octagonal tower (cimbori), with an ambulatory and a polygonal apse.

The old chapter house (today Holy Grail Chapel, 1356–1369), where the canons met to discuss internal affairs, and the Miguelete Tower, known as El Miguelete in Castilian Spanish or Torre del Micalet in the Valencian language, were initially separate from the rest of the church, but in 1459 the architects Francesc Baldomar and Pere Compte expanded the nave and transepts in a further section, known as Arcada Nova, and finally joined both the chapter house and the Micalet with the rest of the cathedral, thereby attaining 94 metres (308 feet) in length and 53.65 metres (176.0 feet) in width.

During the Baroque period, the German Konrad Rudolf designed in 1703 the main door of the cathedral, known as the Iron gate due to the cast-iron fence that surrounds it.

Its concave shape, which causes a unique and studied perspective effect, was distorted during the 20th century because of the demolition of some adjacent buildings (in what was formerly Saragossa Street) to expand the square (Plaza de la Reina).

A project to renew the building was launched during the last third of the 18th century, whose intention was to give a uniform neoclassical appearance to the church, different from the original Gothic style that was then considered a vulgar work in comparison.

Also in 1970, the Houses of Canons, a building attached to the chapels facing Micalet street, were demolished to give the cathedral back its previous appearance, and at the same time elements of little or no architectural value were removed.