La construction de l'église
(appelée improprement Basilique)
 
Nous ignorons quel était le contour de l'agglomération à la fin du XIIIème. Nous savons tout au plus que la cité, avant la construction de l'église, était déjà entourée d'une muraille comme le révèle une enquête de 1301.
C'est en 1295, suite à la découverte des reliques de Sainte Marie Madeleine en 1289, que Charles II d'Anjou décide de la création d'un couvent et de la construction d'une église.
A partir de 1296, les travaux de construction de l'église et du couvent au coeur de la cité, ont certainement bouleversé la topographie urbaine.
Au début il faut libérer de la place : le 4 octobre 1296, le sénéchal de Provence doit prélever une partie des 2000 livres prévus pour financer la construction de l'église (prélevés sur les revenus de la gabelle de Nice), pour payer la démolition des maisons avoisinantes.
Le 5 décembre 1296, de Rome, Charles II ordonne à l'évêque de Sisteron et au sénéchal de Provence de mettre à la tête des travaux maître Pierre de Français, expert dans l'art de construire églises et autres édifices.
Les travaux de construction ont débuté probablement dès le début de l'année suivante.
Début 1301, on procède à l'estimation des coupements nécessaires en vue de percer une rue droite joignant l'église au chemin de Marseille, en un lieu appelé "Luperia" où est érigé une croix en pierre. La neuvième maison estimée confronte la voie publique et le barri. Un rempart existait donc bien avant la construction de l'église.
Le 12 août 1305, l'architecte Jean Baudici prend la succession de Maître Pierre et devient Maître de l'oeuvre de Saint-Maximin.
Le 20 mai 1321 une enquête relative à l'extension antérieure du cimetière autour de l'église révèle que les maisons contigües au cimetière avaient auparavant leur entrée sur la rue de derrière appelée rue des Verriers, et non du côté du cimetière. En outre il est précisé que depuis l'ouverture du chantier de l'église une rue nouvelle située entre les maisons et le cimetière a été créée et les maisons ont maintenant leur porte sur cette rue, donc vers l'église.
Une première tranche de travaux (abside, cinq travées de nef, chapelles correspondantes) est achevé entre 1340 et 1350.
Mais l'investissement et le pillage de la cité en 1357 par les bandes d'Arnaud de Cervole, provoquent pour longtemps l'interruption du chantier.
De plus, en 1388, la sécession de Nice tarit définitivement les ressources prélevées sur la gabelle de cette ville, destinées à la construction de l'église et du couvent.
Le chantier, à partir de la fin du XIVème siècle, n'est alors plus ouvert que de manière épisodique, au gré des donations.
Ainsi, le 30 août 1404, Jean II le Meingre, maréchal Boucicaut, donne 1000 florins pour construire la quatrième chapelle du côté nord (vis à vis de la crypte) et allonger le collatéral gauche d'une travée, en encore 150 florins pour une autre dans la crypte. Cet ouvrage, exécuté par Jacques Caille, Maître maçon de Nans, a pour effet de prolonger l'église à cinq travées de manière dissyméyrique, car la travée de la nef centrale, au dessus de la crypte n'est pas édifiée.
Le prieur Garcias de Falcibus se retrourne alors vers le pape Martin V, de qui il obtient en 1424 une dotation de 1000 florins, pour poursuivre le chantier.
En 1425, lorsque commence le deuxième prieurat d'Abellon, ni le cloître ni le choeur de l'église ne sont achevés et surtout, l'église mence ruine. La pluie y pénètre et s'infiltre de toute part, on peut craindre la destruction de l'édifice s'il n'est promptement restauré.
L'année suivante les travaux de construction du cloître, entrepris en 1408 ,reprennent. Le choeur est installé dans la nef, l'ouvrage des stalles commencé en 1418 par Anthonelle Gervant est poursuivi par Jean Flamenqui, Maître menuisier de Toulon.
Toutefois, l'achèvement du cloître, la couverture du dormitorium, la restauration et l'ameublement de l'église, ne laissent pas de ressources pour prolonger la nef, pas même pour édifier la travée au dessus de la crypte.
En 1432, est abattu le portail provisoire qui fermait l'église. On confie à Maître Thomas Beysset maçon de Marseille la construction d'un portail richement décoré, digne de l'édifice. Il en constituera l'entrée définitive.
Ce n'est qu'en 1508 que les travaux seront repris jusqu'à leur achèvement (sous la forme actuelle) en 1532.