Dossier architecture minimal créé pour intégrer les dossier des verrières.
D’après l'historienne du Moyen Age Jacqueline Caille, le vocable de saint Just et saint Pasteur et de la Vierge Marie (pas encore de Bethléem), est attesté pour la cathédrale dès les années 814 et 844 (plusieurs basiliques et cathédrales se sont succédé à Narbonne depuis le IIIe siècle après Jésus-Christ). Notre-Dame de Bethéem apparaît en 1219 dans l’état des sources connues.
La première pierre de l'édifice fut posée le 3 avril 1272. Le choeur est achevé en 1332. Jean Deschamps est remplacé en 1309 par Dominique et Jacques de Fauran. En 1336, Raymond Aicard prend la suite. Ce dernier termine le transept et les tours jusqu'en 1349.
L'enceinte fortifiée gêne alors la progression du chantier. Le contexte historique fait que la construction s'arrête, laissant l'édifice sans nef.
L'édifice est consacré en 1587.
A également construit la cathédrale de Clermont-Ferrand, puis celles de Toulouse, Limoges (1273) et Rodez (1277).