Le Puy-en-Velay est le lieu d'un ancien culte païen, peut-être celte (on observe une influence celtique sur la frise du chevet) ou orientale (les bas-reliefs du chevet ont adopté des motifs orientaux). Plusieurs légendes expliquent l'intérêt porté par les chrétiens à cet endroit: une femme aurait guéri, sur une dalle phonolithique (qu'on trouve aujourd'hui dans l'église). Elle reçoit l'ordre céleste d'avertir l'évêque saint Paulien de construire une église au Puy.

On raconte aussi qu'un cerf (symbole de l'âme aux prises avec les tentations du monde serait apparu pour délimiter dans la neige les traces du sanctuaire. Enfin, des vieillards auraient apporté aux évêques Vosy et Scutaire les premières reliques de la vierge. Le Puy devient évêché en 593. Jusqu'au IXe siècle, il n'y a pas de pèlerinage vraiment important vers le Puy. A cette époque, le Puy subit la rivalité de l'abbaye de Monastier.

Le porche du For est édifié à la fin du XIIe siècle. Il est surmonté d'une chapelle au XVIe. En 1427, un tremblement de terre rend nécessaire l'ajout d'un gros arc-boutant dans la façade. Celui-ci sera finalement enlevé à la fin du XIXe siècle. Avant le XVIIIe siècle, l'entrée de l'église se faisait par un souterrain qui débouchait presque au niveau du chœur. Un nouveau passage est créé par l'archevêque Gallard et provoque la fermeture de l'ancien passage. Une entrée latérale est percée au XIXe siècle. L'église qui menace ruine subit alors de nombreuses restaurations pas toujours heureuses.

L'architecte Mallay détruit en 1845 une tour défensive du XIIe siècle qui était reliée à la cathédrale par le bâtiment des mâchicoulis. Il fait également disparaître les fresques du croisillon sud. Son successeur, l'architecte Mimey (1865) détruit le chevet et le reconstruit de façon arbitraire. Entre 1885 et 1888, l'architecte Petitgrand reconstitue le clocher pyramidal du chevet. Au XXe siècle, des travaux ont permis de retrouver l'entrée initiale de l'église, par un immense escalier débouchant comme une trappe au cœur de la cathédrale.

Les travées sont séparées les unes des autres par une dizaine de marches. Au fond de la troisième travée, on trouve la pierre des fièvres, un dolmen sur lequel la Vierge serait apparue et qui serait depuis à l'origine de guérisons miraculeuses.

Cette travée est ornée de fresques d'inspiration byzantine (Transfiguration, Vierge en majesté), peut-être peintes par un artiste arabe. L'association entre l'iconographie de la Vierge et celle du Christ s'explique par les destinataires de ce décor.

Celui-ci s'adressait en effet aux pèlerins du jubilé qui avait lieu chaque fois que la fête de l'Annonciation tombait un vendredi saint.

Le porche du For se situe à l'angle méridional du chevet et du transept sud. Il est voûté d'ogives et est ouvert par des arcades à l'est et au sud.

Le programme iconographique des chapiteaux et des culots se lit dans le sens des aiguilles d'une montre à partir d'une main ouverte sculptée dans l'angle du transept et du chevet.
Il s'agit de la main du Créateur, d'où partent des représentations de l'ordre végétal, de l'ordre animal (griffons),

Situé derrière le choeur, de manière originale, le clocher pyramidal date du XIIe siècle. Il a été reconstruit pour la dernière fois en 1887. Il s'agit d'une superposition de sept cubes qui va en diminuant. Le décor, quasiment impossible à observer sans jumelles, se concentre dans les chapiteaux qui se trouvent aux angles des différents niveaux. Au premier niveau, on trouve des ouvriers représentés en atlantes. A l'étage supérieur se pressent des personnages armés et une psychomachie, avec des inscriptions pour les quatre vertus cardinales. Au-dessus on voit un adoubement et une entrée dans un ordre militaire, probablement les Templiers, qui symbolisent le détachement du monde. Au troisième niveau sont montrées des scènes de l'Apocalypse (hommes aux prises avec des dragons).

C'est dans cette galerie qu'on trouve un chapiteau portant un abbé et une abbesse et celui des centaures qui symbolise la luxure.

On y trouve un chapiteau représentant la luxure : une centauresse, qui porte le sceptre de la victoire, fuit devant un centaure.

La galerie sud est la plus ancienne, mais la plus remaniée par les restaurations. Les galeries sont voûtées d'arêtes. Ci-contre, la galerie ouest.