In 313, just after the Edict of Milan, a Constantinian basilica was erected on approximately the same spot as the present cathedral.

Then a Latin basilica was constructed by Bishop Rusticus, who was encouraged in his work by the Gaulish prefect, Marcellus.

Little remains of this building: two Roman columns from the former forum, used in the nave, can now be seen in the present cloister; the lintel and an aedicule of white marble can now be seen in the Lapidary Museum of Narbonne.

The idea to build a Gothic cathedral was a political decision made in 1268 by Pope Clement IV, the former archbishop of Narbonne.

The choir was finished in 1332, but the rest of the building was never completed, as the result of many factors including sudden changes in the economic status of Narbonne, its unusual size and geographical location (to complete it would have meant demolishing the city wall) and financial constraints.