Première étape de 1296 à 1316 : durée 20 ans
Charles II d'Anjou décide de faire construire sur les lieux mêmes de la découverte des reliques, une basilique et un couvent de dominicains. Il confie l'établissement des plans de l'ensemble de la construction au "Magister Petrus Gallicus, protomagister operum curiæ". Or, à cette période, ce protomagister est Pierre d'Angicourt, mais il n'est pas certain qu'il ait effectivement réalisé le début de la construction.
Après quelques années d'arrêt, la reprise des travaux de 1300 à 1316 avec l'architecte du palais des comtes de Provence, Jean Baudici, s'effectue avec une grande ampleur à partir de 1305. Ce renouveau a été possible grâce à la nomination à la tête du couvent de Saint-Maximin, de Jean Gobi qui en sera le prieur de 1304 à 1328.
Deuxième étape de 1320 à 1345 : durée 25 ans
En 1320, le chevet est terminé avec la première travée des trois nefs. Les quatre travées suivantes sont réalisées de 1330 à 1345. L'entrée de la crypte se situe alors en dehors de l'église.
Troisième étape de 1404 à 1435 : durée 30 ans
En 1404, on sait que l'abside et les cinq dernières travées de la nef étaient terminées. Jean II Le Meingre, dit Boucicaut, maréchal de France, décide pour couvrir la crypte de faire édifier la partie nord de la quatrième travée ; la crypte est alors nivelée à hauteur du sol de la nouvelle basilique.
Quatrième étape de 1508 à 1532 : durée 24 ans
Les travaux reprennent sous Louis XII en 1508 avec la nomination d'un nouveau prieur, Jean Damiani, qui exercera le plus long prieurat du couvent durant trente cinq ans de 1508 à 1543. Les travaux de la sixième travée sont repris et terminés en 1513 sous la direction de l'architecte Hugues Caillat. Les trois premières travées sont achevées en 1532 après quelques interruptions dues notamment à la peste. L'inscription gothique du XVIe siècle, au revers de la façade rappelle ces étapes. Les architectes seront Pierre Garcin et son père Jean Garcin. Fin des travaux en 1532
Au XVIIe siècle, l'installation du décor actuel entraîna des altérations importantes qui eurent deux conséquences notables : L'obturation des réseaux des baies des chapelles pour y installer des retables ; la construction de couvertures de tuiles en appentis sur les terrasses qui couvraient les bas-côtés.
À la Révolution, les dominicains sont chassés de leur couvent, le couvent et la basilique sont transformés en un dépôt de vivres, dont Lucien Bonaparte, frère cadet de Napoléon, est responsable. L'homme, brillant orateur, est le président du club des jacobins local. En 1794, il se marie avec la fille de l'aubergiste qui le loge. Lorsque Paul Barras se rend à Saint-Maximin pour faire l'inventaire des biens et œuvres présents dans l'église pour s'en saisir, Lucien sauve les grandes orgues en y faisant jouer La Marseillaise par l'organiste Fourcade. Ému, Barras décide de conserver cet orgue "patriotique". Les révolutionnaires pillent les reliquaires, récupérant les métaux précieux et les bijoux. Les reliques des différents saints présentes dans les reliquaires sont récupérées et sauvées par le sacristain et quelques habitants qui les cachent durant plusieurs années, le temps que la situation politique se stabilise et que le culte puisse reprendre normalement.
Les dominicains ne sont réinstallés dans le couvent de la ville qu'en 1859, après son rachat par le père Henri Lacordaire. Ils reprennent en charge le service de la basilique.
Dès 1839, des travaux avaient été engagés au chevet, comme des graffitis nous l'ont appris, et l'église a été classée au titre des monuments historiques sur la liste de 1840, parmi les monuments les plus prestigieux de France. Les travaux dirigés par le père Lacordaire en 1875 eurent une incidence sur la face du monument : la démolition des maisons de deux étages sur la galerie du cloître et les chapelles nord. La restauration proposée par Henri Révoil connaissait un commencement d'exécution. Les travaux exécutés au XIXe siècle sous la direction des architectes Charles-Auguste Questel et Henri Révoil ont consisté en purges des maçonneries et restitution des profils et des parements par recharges de mortiers de ciment et ragréages de pierre reconstituée dans les parties affectées.
Au cours de la première moitié du XXe siècle, l'architecte et archéologue Jules Formigé s'intéresse à la basilique, mais procède surtout à des fouilles et à la présentation de la crypte que Révoil avait décorée dans le goût de son temps en 1884. Son fils Jean Camille Formigé entreprit des travaux au-dessus du bas-côté nord, en supprimant les appentis du xviie siècle et en exécutant une terrasse couverte de dalles de ciment armé, source de déboires.
Après la Seconde Guerre mondiale, Paul Colas put intervenir sur les fenestrages du bas-côté nord, de l'absidiole nord, mais les travaux furent interrompus. « L'état de l'ancienne basilique royale était devenu si inquiétant que le seuil d'alerte est dépassé depuis longtemps », rapportait l'inspecteur général des monuments historiques François Enaud le 25 mai 1977. Dès 1975-1976, des chutes de pierres provenant des nervures des voûtes sur croisée d'ogives et doubleaux s'étaient produites, et une campagne de purges et de confortations tout à fait provisoires étaient exécutées.
La cause essentielle des désordres dont souffrait cet édifice était l'eau qui s'infiltrait par les couvertures, par les dispositifs d'évacuation des eaux pluviales et par les joints des murs. Ces eaux affaiblissaient les appuis en lavant les mortiers des blocages internes. Elles modifiaient les conditions d'équilibre des voûtes et les arcs pèsent plus lourd, donc poussaient davantage en écrasant les pierres atteintes, souvent masquées par les ragréages du xixe siècle.
Le programme de mise hors d'eau et de confortation structurale a alors été entrepris. Les travaux ont consisté, en partant de l'angle sud-ouest, à refaire la couverture du bas-côté, en reprenant les évacuations d'eaux pluviales qui, depuis les fenestrages, traversent le comble en appentis, à rejointoyer les murs et les contreforts et leurs appuis. Un pare-gravois a dû être mis en place devant la façade à la suite de chutes de pierres. La façade occidentale inachevée depuis 1530 a été confortée en 1986-1987.
Jean-Claude-Yvan Yarmola, architecte en chef des monuments historiques, maître d'œuvre des travaux réalisés dans le cadre d'un plan pluriannuel d'intervention, établi pour la période 1986-1993, par la conservation régionale des monuments historiques, la commune et le conseil général du Var concluait « qu'en l'état des travaux, nous visons à réparer les dégâts dus à des décennies de manque d'entretien, mais que l'effort collectif fourni pour sauvegarder ce monument doit être poursuivi dans l'intérêt commun qui dépasse celui de la Provence ».
Le 4 mai 2014, le prêtre de la basilique, Florian Racine, annonce lors de sa messe, la découverte, dans la basilique, d'un crâne susceptible d'être une relique de saint Sidoine. En 2012, puis 2016, le curé de la paroisse demande à faire ériger l'édifice au titre de basilique mineure. Communément appelé « basilique » par la population et le clergé, depuis sa création, l'édifice n'en avait pas reçut le titre du Vatican. En 2017, le dossier de demande est accepté par les autorités vaticanes et le titre officiellement décerné.
En 2017, le diocèse demande à une équipe de scientifiques d'effectuer une reconstitution 3D du visage de Marie-Madeleine à partir de son crâne conservé dans la basilique. Une expertise récente du crane a rapporté que ce crane est celui « d’une femme de petite taille, de type méditerranéen, âgée d’une soixantaine d’années ». En 2021, le laboratoire Géosciences Paris-Saclay mène une prospection géophysique à la basilique Saint-Maximin-la-Sainte-Baume sur la demande du diocèse de Fréjus-Toulon.