L'occupation de la zone est ancienne : on y a découvert des outils attribués au Paléolithique moyen, un four, bien conservé, du Vérazien (Néolithique, III millénaire av. J.-C.), et des objets de l'âge du bronze. Une villa gallo-romaine (propriété d'un Marcellus ?) dont dériverait le toponyme de Marceille a peut-être existé au voisinage.
L'église apparaît probablement dans les textes en 1011 associée à la villa de Flassian, et de façon plus certaine en 1137. La Vierge noire, statue de bois qui est vénérée dans le sanctuaire, est datée du XI siècle. La construction de l'édifice actuel a été entreprise au début du XIV siècle ; son plan à nef unique rappelle quelque peu celui de l'église Saint-Vincent de Carcassonne. À la même époque les revenus du prieuré sont attribués au collège de Narbonne à Paris.
Jusqu'au XVII siècle, le soin d'accueillir les pèlerins fut laissé à des ermites. Cependant, François Fouquet, quand il fut nommé archevêque de Narbonne, pensa à confier aux Doctrinaires la conduite d'un séminaire et d'une maison de missionnaires : il obtint des consuls de Limoux de les installer à Notre-Dame de Marceille. Ce changement fut mené à bien par son successeur Pierre de Bonzi en 1674 : il mit alors deux prêtres de la doctrine chrétienne qu'il chargea de recevoir les pèlerins et les ecclésiastiques en retraite spirituelle.
L'église fut élevée au rang de basilique mineure le 5 février 1905.
En octobre 2007, alors que l'église était en travaux, la Vierge noire a été décapitée, sa tête et son manteau ont été volés.