L’origine du vocable de cette basilique provient de la dévotion portée par les nouveaux habitants occitans du Puy-en-Velay arrivés à Estella pendant la seconde moitié du xi^e siècle sous l’influence du chemin de Saint-Jacques-de-Compostelle.

La tradition populaire raconte qu’en 1085, la Vierge est apparue devant un groupe de bergers voisins du bourg d’Abárzuza alors qu’ils gardaient leur troupeau. Quoi qu’il en soit, la première référence documentaire de ce sanctuaire date de 1171. Trois ans plus tard, en 1174, l’évêque de Pampelune cédait l’église à la confrérie des soixante confrères de Saint-Jacques pour rebâtir le temple.

À partir du xiii^e siècle, la basilique du Puy bénéficie de l’appui des Rois de Navarre, ceux-ci lui présentent divers hommages, offrandes et autres bénéfices, en outre le moulin du teinturier tenu par la communauté juive sur la rivière Ega.

De ses premiers siècles, elle en conserve encore l’image gothique de la Vierge (xiv^e siècle) et les merveilleuses peintures de style gothique international qui décorent l’Arche qui l’abritait.

C’est ici que furent fusillés, sur ordre du général carliste Maroto, les cadres militaires carlistes qui s’opposèrent aux négociations et qui aboutirent, en 1839, à la Convention d’Ognate (en espagnol « el Abrazo de Vergara »). Déjà, durant la Deuxième Guerre carliste, en 1874, le prétendant au trône, Charles IV d’Espagne (Carlos IV) fit don à la basilique de son sabre personnel en faveur de la cause carliste. Le sabre se conserve encore aujourd’hui parmi d’autres pièces qui composent le trésor de la Vierge.

La dégradation du bâtiment baroque de l’église entraina la construction d’un nouveau temple. En 1929, l’architecte Victor Eusa se chargeait de la conception du bâtiment actuel de style éclectique et néogothique, dont les travaux furent achevés en 1951.