Les Carmes, un des quatre ordres mendiants avec les Augustins, Franciscains et Dominicains, apparaissent les premiers à Marseille et en France. En effet vers 1238 des moines d’origine provençale du Mont Carmel sont chassés de la terre sainte et s’installent aux Aygalades. Ce quartier de Marseille est à l’époque un site rupestre et éloigné de la ville, conforme à la vocation érémitique des moines.
En 1285 ces religieux obtiennent la permission de s’établir à l’intérieur de la ville et fonde un nouveau couvent sur la colline Roquebarbe, actuelle butte des Carmes, afin de se trouver plus près des masses populaires à évangéliser. La construction de ce couvent et de son église est effectuée en partie grâce à un legs du 2 juin 1361 de Guillaume André, prieur de leur ordre.
L’édifice menaçant ruine est reconstruit au XVIIe siècle. La première pierre est posée le 10 novembre 1603 par l’évêque Mgr Frédéric Ragueneau et le presbytère est terminé en 1619. Le 31 octobre 1629 les consuls de Marseille, Philippe de Félix, seigneur de la Reynarde, Lazarin de Servian et Elzéard Faravel, effrayés par la peste qui désolait une grande partie de la Provence et la ville d’Aix-en-Provence, font présent aux religieux des Grands Carmes et au nom de la ville, d’une lampe d’argent pour brûler constamment devant la statue de la Vierge. Ils s’engagent également à donner annuellement au couvent une somme de dix-huit livres pour l’achat de l’huile nécessaire à l’alimentation de la lampe.
La première pierre du clocher est posée le 31 mars 1640 en présence des consuls et de Mgr Jean-Baptiste Gault. Ces reconstructions sont financées grâce à la confrérie de Notre-Dame du Saint Sépulcre et à la générosité du baron Jehan de Marelhan (ou Marillan) qui voulut attacher son nom à cette pieuse fondation et fit édifier son tombeau dans l’église. En 1655 la confrérie de Notre-Dame du Saint Sépulcre dote l’église d’une statue d’argent qui passait pour être un chef d’œuvre de l’art en ce genre.
La vie du monastère du milieu du XVIIe siècle à la Révolution est peu connue. En 1790 le couvent des grands Carmes est fermé et les frères expulsés. Le 20 février 1790 le père Rolland, ancien prieur, est pendu ainsi que trois de se compagnons. C’est grâce aux habitants du quartier que cet édifice n’est pas démoli, mais conformément au décret de l’Assemblée législative des 14 et 22 avril 1792 les cloches de l’église sont démontées et envoyées à la fonte. Il en est de même pour la lampe d’argent et la statue d’argent de la Vierge. En cette même année 1792 une inscription en mémoire du bataillon des Marseillais qui se distinguèrent à la journée du 10 août à Paris est placée sur la façade de l’église.
Le service religieux est assuré par des prêtres ayant prêté serment à la Convention. Après avoir pris le vocable de Saint Étienne, l’église prend en mai 1800 le nom de Saint Lazare après le transfert des reliques de ce saint en provenance de la Major au moment de la fermeture de la cathédrale. Elle reprend son nom des Grands Carmes le 18 juillet 1802 après le concordat signé entre Pie VII et Napoléon.
Parmi les différents curés de la paroisse, il faut retenir le nom de Louis Decanis qui est nommé le 19 octobre 1862. Très actif il entreprend la restauration de son église et réalise peinture et dorure à profusion. Il commande des statues de plâtre aux ateliers de Louvain et de Munich ainsi que le tombeau du saint Sépulcre qui est taillé par la maison Virebaud de Toulouse. Le curé Decanis est de plus un prêtre de caractère. En effet pendant la guerre de 1870 l’évêque de Marseille Mgr Place demande à son clergé par lettre circulaire du 18 novembre 1870 de faire un don volontaire de quelques cloches pour venir en aide à la patrie : le curé Decanis désirant conservé les cloches de son église, propose au préfet en remplacement la fourniture d’une mitrailleuse d’une valeur de 500 Frs payée par les paroissiens. Cette proposition est acceptée. Le curé Decanis meurt le 6 août 1882.
En 1897 le dôme du chœur et une partie du clocher s’effondrent. La municipalité refuse de prendre en charge la réparation ; le clocher est alors réduit et le sanctuaire est caché par un grand mur derrière l’autel.