Le cartulaire de l'abbaye de Saint-Victor de Marseille fait état d'une église Sainte-Maxime s'élevant au 11e siècle à l'embouchure du Préconil. Une chapelle figure à l'emplacement actuel de l'église sur un plan datant des années 1628-1632. Sainte-Maxime est érigée en paroisse le 21 juillet 1672.

En 1748, l'historien Girardin (cité sur le site de la paroisse) écrivait que c'était une simple chapelle en bord de mer alors que le village s'agrandissait de jour en jour. En 1761, demande est faite aux consuls d'étudier les divers plans proposés pour l'agrandissement (il s'agit en fait plutôt d'une véritable reconstruction) de l'église paroissiale. La même année, le plan d'agrandissement est approuvé avec des modifications consistant dans la construction d'une voûte en brique et d'un clocher. Les travaux sont commencés au début de 1762 mais sont arrêtés faute d'argent, puisque la même année un rappel est fait à l'archevêque de Bourges, seigneur de Sainte-Maxime en qualité d'abbé du Thoronet, de sa promesse de contribuer pour un tiers à la dépense d'agrandissement de l'église. Il est fait mention du souhait d'obliger les entrepreneurs à reprendre les travaux de l'église pour les terminer au plus tôt. En 1773 est mentionnée l'ouverture d'un œil-de-bœuf (l'oculus de la façade antérieure ?). Les travaux ne semblent toutefois jamais avoir été bien achevés car en 1774, lors de la construction de la maison curiale qui lui était adossée, il est fait mention de la "nouvelle nef de l'église" à réparer car elle menace ruine. Ces travaux sont effectués par Philippe Radice, entrepreneur. En 1787, on note l'approbation de comptes pour la réparation à la toiture de l'église et aux fenêtres.

En 1843, une horloge est placée au centre d'un fronton construit au-dessus du clocher devant le campanile en fer forgé. L'église est de nouveau agrandie en 1851 de toute la surface du chœur, puis en 1869 avec l'ajout des chapelles du Sacré-Cœur et de Sainte-Maxime, entre les contreforts, à l'est.

D'importants travaux de transformation ont à nouveau lieu en 1938. Ils sont l’œuvre de l'architecte René Darde. Le presbytère qui jouxtait l'église à l'ouest est supprimé et l'on construit à la place un ensemble à la volumétrie composite constitué de deux chapelles, d'une sacristie à l'arrière accessible par le chœur, et d'une autre chapelle plus basse formant une excroissance dans l'angle sud-ouest. Les murs de l'ancien presbytère ont peut-être été conservés car les matériaux et la mise en œuvre sont très proches de ceux de la chapelle, les deux baies géminées ont manifestement été percées dans un mur existant et la trace d'un arc plein-cintre pourrait correspondre à la fenêtre de la travée droite du premier étage du presbytère. Les autres interventions de Darde consistent au remplacement du campanile en fer forgé du clocher par un troisième niveau maçonné couvert en pavillon et abritant l'horloge. L'ensemble est alors complétement crépi. A l'intérieur, Darde construit la tribune de l'orgue au-dessus de l'entrée et une niche à l'arrière du maître-autel, saillant sur l'extérieur et destinée à accueillir le groupe sculpté (Calvaire) alors en place. Cet ensemble a vraisemblablement été supprimé lors de l'installation des nouvelles verrières dans les années 1950 et remplacé par une grande rose.

L'église a été restaurée en 1990-1993. Le clocher a retrouvé son apparence d'origine ; l'horloge et la surélévation ont été supprimées et un campanile en fer forgé a été remis en place. Les murs extérieurs ont été décrépis et la pierre laissée apparente, ce qui n'était pas l'état d'origine puisqu'ils étaient crépis à l'origine. C'est à ce moment qu'a été peint le Christ bénissant du tympan.