Nous ne possédons aucun document iconographique de la cathédrale originelle. Mais nous savons qu’elle a existé. Elle était en service en même temps que le baptistère érigé entre les IVe et Ve siècles.
L’édifice existera jusqu’au XIe siècle. Il subit comme le baptistère, les invasions des sarrasins au moins à trois reprises. Par nécessité, il est proche du baptistère, et donc est implanté sur le lieu même de l’actuelle cathédrale. C’est peut être Proculus, le deuxième évêque « historique » de Marseille qui le fait construire à partir de 401. Il existe encore quand Pons II, en 1050, entreprend la consolidation du chœur qui tombe en ruines ( Ruffi ). Le grand historien de Marseille nous apprend aussi que cette cathédrale dédiée au commencement à saint Lazare, prend par la suite le nom de Très-Sainte Vierge. Les chartes du temps de Charlemagne la nomment « ecclesia sanctoe Marioe » ou « Nostroe Dominoe antique Sedis », parce qu’elle a toujours été le siège de l’évêque. Et Ruffi parle souvent de l’église Majeure ou de l’église cathédrale.
« En l'année 813, Charlemagne fît convoquer un concile dans la ville d'Arles, pour dresser des règlemens sur la police et la discipline ecclésiastiques. En effet, les Pères qui assistèrent à cette assemblée ordonnèrent que les ecclésiastiques des cathédrales se fermeroient dans les cloîtres pour y vivre séparés de la fréquentation du monde; et afin qu'ils fussent gardés exactement, on députa dans les provinces des commissaires apostoliques pour les obliger à suivre cette forme de vie retirée, et à observer les constitutions qui furent dressées dans ce concile.
Ce grand empereur étant décédé, Louis-le-Débonnaire, son fils, fit aussi assembler, l'an 817, un concile à Aix-la-Chapelle pour le même sujet dans lequel se trouvèrent quantité d'évêques et d'abés. Ce prince leur fit composer une règle sur les écrits de S. Isidore , de S. Ierôme, de S. Augustin , et de quelques autres SS. Pères , laquelle permettoit aux chanoines de manger de la viande , de porter des chemises , de posséder le bien des églises, de donner et recevoir leurs biens propres ; et afin qu'elle ne fût pas ignorée , Louis la fit envoïer aux Métropolitains avec !a mesure du vin et le poids du pain pour résoudre ce qu'on on devait donner aux ecclésiastiques. Ce qui fut pour lors observé; et la plus grande partie des cathédrales firent gloire de se soumettre sous le joug de celle régle..
De sorte, que j'infère de là que. comme Marseille et la Provence étoient sous le pouvoir de Charlemagne et, de ses fils, et que l’archevêque d'Arles étoit le métropolitain de notre évêque; cette vie canonique et régulière fut alors infailliblement reçue dans notre ville et observée dans la cathédrale, ce qui est confirmé en quelque façon par un titre de l'an 1163. »
Malgré la réhabilitation de 1050, l’église Majeure est dans un état fort délabré à la fin du XIe siècle, si bien que Pons II entreprend sa reconstruction complète.
Les démolitions et les fouilles en vue de la construction de la nouvelle Major (à partir de 1854), mettent à jour des tombes creusées dans une sorte de tuf, sur plusieurs rangées, parallèles du nord au sud. Elles sont de forme parallélipédiques, plus étroites aux pieds. Dans l’une d’elles, on trouve une médaille du bas empire ainsi qu’un pot en grès. Ces tombes datent du début des premiers chrétiens. Le pot était destiné à contenir de l’eau bénite.