En 1070, le vicomte de Millau, Béranger, donne à l'abbaye bénédictine Saint-Victor-de-Marseille "l'église dédiée à la Mère de Dieu qu'il possédait dans le bourg de Millau, avec tout le terrain nécessaire pour bâtir un monastère bénédictin". L'église Sainte-Marie, son premier vocable, est consacrée le 25 août 1096 par le pape Urbain II, revenant de Clermont où il avait prêché la 1ere croisade. Durant les guerres de religion, en 1561, l'église et le prieuré attenant sont pris d'assaut et partiellement abattus par les protestants millavois. Les statues, images pieuses et instrument de culte sont détruits. Les moines sont dispersés. Entre 1561 et 1601, Notre-Dame est abandonnée à la ruine avec la suppression du culte catholique. Il faut attendre 1631 et Vincent Melchior de Solargues devenu curé pour voir sa remise en état. La reconstruction est successivement confiée à Jacques Baudoin (1633-41), maître architecte et sculpteur du Puy-en-Velay, qui élabore les plans, puis à Jean Favières, maçon de Broquiès et Julien Baudoin, maître maçon de Sainte-Eulalie (1641-69). Ils reconstruisent notamment la voûte de la nef "voûtée en berceau d'une muraille à l'autre", supprimant alors les colonnes médianes d'origine et le clocher sud. L'église est réouverte en 1646, avant l'achèvement des travaux de gros-oeuvre, vers 1657. Une nouvelle chapelle de l'Assomption est fondée en 1683 (la première avait été fondée en 1492), celles de Saint-Caprais date de 1700, celle de Saint-Sébastien de 1715. Les tribunes latérales sont édifiées en 1759-1760. Pendant la Révolution, l'église est transformée momentanément en Temple de la Raison. Puis dans la deuxième moitié du 18e siècle sont ajoutées d'autres chapelles, celles du Sacré-Coeur (1822 ; détruite), du Rosaire (1826), de Sainte-Philomène et Saint-Joseph (1846), des Fonts-Baptismaux (1850 ; aujourd'hui détruite). Les vitraux actuels du choeur datent de 1869. C'est en 1939 que les fresques du choeur sont réalisées par le peintre Jean Bernard. L'église est classée au titre des monuments historiques en 1945. Les verrières actuelles de la nef sont réalisées dans les années 1980 par le peintre-verrier Claude Baillon.