Selon la légende, qui prend des libertés avec la vérité historique, Quitterie était la fille d'Aetius, roi wisigoth de Toulouse[4]. Refusant la main de Germain, l'exécuteur des basses œuvres de son père, elle s'enfuit à Aire-sur-l'Adour déguisée en cavalier pour échapper aux sollicitations du prétendant et à la colère de son père. Sa fugue intervint peu de temps après sa conversion au christianisme accompagnée d'un vœu de chasteté. Germain finit par la retrouver et la décapita.
La légende dit que quand sa tête toucha terre, une fontaine jaillit. Quitterie aurait pris sa tête bien lavée dans ses bras pour la déposer en haut du plateau du Mas, où se trouve aujourd'hui son sarcophage (dans la crypte de l'église Sainte-Quitterie d'Aire).
L'évêque, du nom de Faust, fit le jour même un prêche, à la suite duquel toute la ville d'Aire se convertit au christianisme, y compris Germain.
Tout près de l'église d'Aire coule aujourd'hui une fontaine à laquelle on attribue la vertu de guérir les maux de tête ainsi que la rage (on la représente souvent avec un chien à ses pieds tirant la langue). De nombreuses fontaines des Landes et de la Charente (Aussac,Chadurie) supposées avoir les mêmes vertus, sont placées sous le patronage de la sainte. Quitterie est depuis un prénom typique des Landes et du Sud-ouest en général. La mère de saint Gaudens, martyr du VIe siècle en Comminges, s'appelait aussi sainte Quitterie, mais il n'y a aucun rapport entre les deux, si ce n'est que le nom ancien de la ville de Saint-Gaudens était le Mas Saint-Pierre, comme celui d'Aire-sur-l'Adour était le Mas d'Aire.