L’abbaye de Quarante fut d’abord la simple église d’un bourg, mentionnée pour la première fois dans un acte de 902. A la fin du Xème siècle la famille vicomtale de Narbonne et les archevêques de la métropole narbonnaise qui lui étaient liés prirent cette église sous leur protection et bientôt une communauté de douze chanoines réguliers la desservit ; elle prit ensuite le titre d’abbaye. L’église a sans doute été reconstruite pour pouvoir accueillir les chanoines à la fin du Xème siècle : l’archevêque Ermengaud procéda à sa dédicace en 982. La construction de cet édifice a dû s’achever au début du XIème siècle, car en 1016 l’évêque Urbain de Béziers, à la demande de l’archevêque, vint y consacrer une chapelle dédiée à saint Martin. Il ne reste plus grand-chose de cette première église, sauf un fragment d’autel et la base des bas-côtés et de la façade Sud, car l’édifice a été reconstruit au milieu du XIème siècle : une nouvelle dédicace a eu lieu en 1053 par les évêques de Béziers et d’Agde et l’archevêque Guifred de Narbonne, fils du comte de Cerdagne et neveu de l’abbé Oliba de Ripoll et Saint-Michel de Cuxa. Les procédés techniques en usage en Catalogne et en Roussillon pénètraient alors en Languedoc, et l’église abbatiale de Quarante témoigne du premier art roman méridional, caractérisé par un chevet de type lombard 
et des incrustations fréquentes de basalte noir, le plus souvent en cordon au-dessus des arcatures des fenêtres. 
Le transept est particulièrement long, et le chevet est constitué d’une vaste abside semi-circulaire flanquée de deux absidioles.
Les chanoines de Quarante étaient complètement sous la tutelle de l’archevêque. L’année qui suivit la nouvelle dédicace de Sainte-Marie de Quarante, en 1054, l’archevêque Guifred, accusé de simonie, de vol et de parjure, fut excommunié. Il était l’archétype du prélat indigne que dénonçait le courant réformiste qui allait triompher dans l’Eglise et qu’on appelle la réforme grégorienne.