Le premier évêque du Valais, saint Théodule, bien attesté dans l'histoire de l'Eglise pour sa participation au Concile d'Aquillée en 381, avait son siège épiscopal à Octodure, aujourd'hui Martigny. C'est lui qui rassembla les restes des martyrs thébains, au lieu dit Vérolliez, et les déposa dans un premier sanctuaire au pied de la falaise rocheuse d'Agaune, vers 370 après J.-C.
L'endroit est sacré: c'est un lieu de prière et de sépulture. On y trouve un sanctuaire dédié aux Nymphes, à côté d'une source vive qui chante aujourd'hui encore les bontés du Créateur. Bientôt les pèlerins accourent: le sanctuaire est agrandi et on construit un hospice pour les accueillir. Vers l'an 500, la communauté d'Agaune paraît avoir eu pour chef saint Séverin qui mourra à Château-Landon alors qu'il avait été appelé au chevet du roi Clovis, car il avait une réputation de thaumaturge.
A la domination romaine succéda bientôt le Royaume des Burgondes. L'un de ses princes, Sigismond, fonda le monastère qui intégra la première fondation de saint Théodule. D'autres groupes de moines provenant de l'Ile-Barbe et de Grigny (région lyonnaise), de Condat, l'actuel Saint-Claude, et de Romainmôtier (région du Jura), formèrent, avec la communauté locale, un groupe de cinq chœurs qui inaugurèrent en Occident la "Laus perennis". Cette Laus perennis fleurit plus tard dans d'autres monastères des Gaules, à l'imitation d'Agaune. Le monastère fut inauguré solennellement le 22 septembre 515. Saint Avit, évêque de Vienne sur le Rhône prononça l'homélie. En 524, Sigismond fut massacré par le roi franc Clodomir. On rapporta d'Orléans ses restes pour les déposer dans la chapelle Saint-Jean, devenue plus tard l'église paroissiale Saint-Sigismond à Saint-Maurice.