Selon la tradition, Marie-Madeleine (ou Marie de Béthanie, sœur de Marthe et de Lazare) fuyant les persécutions d'Hérode, aurait trouvé refuge en Provence en compagnie de son frère et de sa sœur. Après avoir débarqué aux Saintes-Maries-de-la-Mer, elle aurait occupé pendant trente ans une grotte du massif de la Sainte-Baume pendant qu'elle évangélisait la Provence. À sa mort, elle aurait été ensevelie à Saint-Maximin-la-Sainte-Baume. Devenu célèbre son tombeau qui se serait trouvé dans la crypte actuelle de la basilique, sera gardé par des moines cassianites (disciples de saint Cassien) venus de l'abbaye Saint-Victor de Marseille. Au VIIIe siècle, les invasions sarrasines obligent les religieux à combler la crypte qui abritait le tombeau afin de mettre à l'abri les précieuses reliques. Le culte de la sainte reste cependant vivace.

Le souvenir de cette sépulture ne s'étant pas perdu, le prince de Salerne, Charles II, fils de Charles Ier et de Béatrice de Provence, fait entreprendre en 1279 des recherches pour retrouver les reliques de sainte Marie-Madeleine à laquelle il voue une grande dévotion. Ces recherches aboutissent à la découverte d'une tombe paléochrétienne, la crypte actuelle, contenant des ossements qui auraient appartenu à la sainte. Charles II, comme il l'affirmait lui-même, aurait agi par « inspiration divine ». Philippe de Cabassolle parle, dans son Libellus hystorialis, de « céleste inspiration ». Charles II devenu comte de Provence et roi de Naples, se rend en avril 1295 auprès du pape Boniface VIII apportant avec lui les procès-verbaux rédigés par les évêques de Provence authentifiant sa découverte. Il obtient du pape des bulles qui accordent des indulgences aux visiteurs et certifient l'authenticité des reliques. Cette confirmation était d'autant plus précieuse que la basilique de Vézelay affirmait posséder le corps de Marie-Madeleine. Le pape décide également de confier la garde de Saint-Maximin et de la Sainte-Baume aux frères prêcheurs de saint Dominique en lieu et place des moines bénédictins de l'abbaye Saint-Victor.