Volgens de legende is de stad gesticht in de 5e eeuw. De Maagd Maria zou toen verschenen zijn bovenop een rots om een vrouw die leed aan hevige koorts te genezen. Op de plaats van deze verschijning, "la pierre des fièvres" (de koortssteen), werd dan een heiligdom gebouwd, de latere kathedraal. Le Puy-en-Velay werd een mariaal bedevaartsoord waar mensen heentrokken om genezing te vinden. Rond dit bedevaartsoord op de Mont Anis ontwikkelde zich de stad. Vanaf de 10e eeuw ontwikkelden zich ook de bedevaarten naar Santiago de Compostella en de stad werd een verzamelpunt voor deze bedevaarten. Hieraan dankte de stad haar rijkdom. In de 10e eeuw werd bovenop steile rots de kapel Saint-Michel d'Aiguilhe gebouwd door bisschop Godescalc en het kathedraalkapittel. In de 12e eeuw werd de kathedraal uitgebreid tot boven de afgronden van de rots waarop ze gebouwd is om de talrijke pelgrims te kunnen ontvangen. Daarnaast ontwikkelde zich in de stad ook een nijverheid van goudsmeedkunst en kantproductie. Verder waren er in de stad leerlooierijen en smederijen. Ook als handelsplaats was Le Puy-en-Velay belangrijk en goederen werden aangevoerd met muilezels. De rijke burgers van de stad bouwden statige burgerhuizen.

In 1860 werd bovenop de Rocher Corneille een 22,7 meter hoog Mariabeeld opgericht, Notre-Dame de France. Hierbij werd het metaal van 213 omgesmolten Russische kanonnen gebruikt, geschonken door Napoleon III.[1]