Bâtie sur les ruines de l'antique "villa lata", la première ville de Saint-Maximin dépend durant le moyen-âge d'un petit château, le "Castrum Redonas" situé sur une éminence proche.
Après, que le comté de Provence soit passé de la maison catalane à celle d'Anjou, une nouvelle ville est bâtie par Charles II autour de la Basilique gothique consacrée au culte de Marie-Madeleine, Sainte patronne de la Provence.