Le diocèse a été fondé vers 374 à la périphérie de la ville romaine. Nous n'avons aucune nouvelle des premières constructions, si ce n'est que Grégoire de Tour mentionne au 6e siècle qu'une "basilique miraculeuse" a été érigée sur les tombes de Nazarius et de Celse à Embrun. Un baptistère, mentionné dans une source douteuse, aurait pu compléter la cathédrale. Des destructions par les Lombards en 575 et par les Sarrasins en 973 sont attestées. A l'époque carolingienne, Embrun, qui avait entre-temps été subordonnée à Arles, retrouva son indépendance en tant qu'archevêché vers 829. Un nouveau bâtiment a certainement été construit à cet effet. Un édifice roman a été érigé vers 1010. L'édifice actuel date de 1151. Il possède une tour nord en façade. La question de savoir si l'idée d'une extrémité orientale à trois absides, telle qu'elle apparaît dans la construction actuelle, a été reprise d'un prédécesseur carolingien sous influence rhétique reste ouverte.