Согласно преданию, восходящему к св. Евхарию Лионскому, местом дислокации легиона была Фиваида, в Египте. Отсюда этот легион был отправлен императором Максимианом в Галлию, для подавления восстания багаудов. Командовал легионом св. Маврикий (Mauritius). Его помощниками были Кандид (Candidus) и Экзюперий (Exuperius), которые тоже почитаются святыми. После разгрома багаудов легион был отведён в город Агаунум, нынешний Сен-Морис д’Агон (Saint-Maurice или Saint-Maurice-en-Valais), а император Максимиан издал приказ, чтобы все в честь победы совершали жертвоприношения римским богам. Легионеры твёрдо и единодушно отказались от этого, за что были подвергнуты децимации и предупреждены, что император не остановится пока приказ не будет выполнен. Тогда св. Маврикий обратился к легиону с призывом не поддаться угрозам и быть верными клятве, данной при крещении, по примеру уже казнённых товарищей. Его слова нашли отклик в сердцах этих отважных солдат и от имени легиона было отправлено письмо Максимиану следующего содержания:
Так как акт устрашения не возымел действия, его многократно повторяли до тех пор пока не был истреблён весь легион.
Согласно посланию Евхария Лионского, тела Агаунских мучеников были обнаружены и идентифицированы епископом города Октодурума (нынешний Мартиньи) Феодором в 350 г. Последний построил в их честь базилику в Агаунуме, которая стала местом паломничества и чьи остатки можно наблюдать и сейчас. Она стала частью аббатства, построенного в 515 году на земле, пожертвованной Королем Бургундии Сигизмундом. Это же послание является самым ранним упоминанием об Агаунских мучениках, «которые прославили Агаунум своей кровью» и описывает последовательность свидетельств за период в 150 лет, со времени мученичества до времени Евхария. Он совершил паломничество в Агаунум. Евхарий упоминает свидетельства паломничества и дорогих подарков от верующих из разных провинций империи, различные чудеса, такие как изгнание бесов и случаи излечения, а сам рассказ о мучениках предваряет словами:
Именно Евхарий говорит, что численность легиона была равна «шести тысячам и шестистам мужам».
Писатель шестого века Григорий Турский в книге «Liber in gloria martyrum» («Книга о славе мучеников») упоминает базилику в Кёльне,
Предание о Фиваидском легионе и житие св. Маврикия стали очень популярными в Средневековье и упоминались в «Золотой легенде» Иакова Ворагинского. В этом сборнике число легионеров равняется 6666.
Против историчности Фиваидского легиона приводят следующие доводы: