Maurin Ier, chanoine de Narbonne avant d’en être archevêque, pose la première pierre de la nouvelle église de Saint-Just et Saint-Pasteur en l’an 1271. Cette église, construite par Charlemagne et détruite par le temps et les ravages de la guerre, est rebâtie sous le règne de Saint Louis. Le pape Urbain IV envoie de Rome la pierre fondamentale bénie et ornée d’une croix d’or. Le chœur est  achevé en 1332. 
Mais la poursuite des travaux exige que l'on abatte une section de l'enceinte fortifiée. Les consuls de Narbonne s'y opposant, il s'ensuit un long procès. Par la suite, l’épidémie de peste de 1348 et le raid du Prince Noir en 1355 ont des répercussions sur le développement économique de la région. Le projet est alors abandonné. En 1840, Viollet-le-Duc tente brièvement de le relancer. Le transept et les premières chapelles de la nef resteront inachevés.
 
L'édification de la cathédrale est un des projets les plus ambitieux du royaume de France du XIIIe siècle. Saint-Just et Saint-Pasteur possède un chœur aux dimensions imposantes : 40 m de large, 60 m de long. Les voûtes s'élèvent à 41 m ; seules celles de Beauvais et d'Amiens présentent une hauteur supérieure. Le cloître est adossé à l'enceinte fortifiée et relié au palais des archevêques - Palais Vieux d'origine romane et Palais Neuf de style gothique.
 
Conçu pour prendre place dans la cathédrale achevée, l’orgue de Christophe Moucherel (1741) est également de dimensions impressionnantes. Il est accroché au fond du chœur, en porte-à-faux au-dessus des stalles.