Een eerste kerk werd vermoedelijk eind 10de of begin 11de eeuw gebouwd bij een handelsnederzetting. Ze werd ingeplant bij de buitenbocht van de pas tussen 1963 en 1970 gedempte Scheldekronkel aan de Smallendam-Meerspoort. Deze kerk werd de Onze-Lieve-Vrouw ter Kauwen genoemd, wellicht naar de kauwen of kraaien die zich in de toren nestelden.

In 1150 werd de kerk heropgebouwd na een brand in 1126. De wederopbouw gebeurde in Doornikse steen. De kerk had een groot rechthoekig koor en kruisingstoren. Het koor werd begin 13de eeuw uitgebreid met een zijkoor aan de noordzijde en hoektorentjes. Een identiek zijkoor aan de zuidzijde werd toegevoegd begin 14de eeuw. In 1407-09 werd ter ere van Jan zonder Vrees de absis bijgebouwd.

In 1414 besliste de stadsoverheid de kerk te vergroten zodat het kon wedijveren met de kerken en kathedralen der grote steden. Men begon met de bouw van het schip in Brabantse gotiek en in Balegemse zandsteen, alsook met de bouw van de toren. Door herhaald geldgebrek gingen de werken maar traag vooruit. In 1534 vielen de werken zelfs volledig stil. De geplande verbouwing van het koor en de uitbreiding naar de markt toe is nooit uitgevoerd geworden.

Men kan duidelijk zien dat de kerk de samenvoeging is van een jonger hoogschip met basilikale opstand (het middenschip is hoger dan de zijbeuken en ertussen bevinden zich bovenvensters) en een veel oudere en lagere koorpartij dat bijna een hallekerk op zich is.

In de 16de eeuw werd het interieur verrijkt . Door de beeldenstorm van 1566 en later werd echter gans de inboedel vernield. Het gebouw zelf bleef gespaard omdat het als tempel gebruikt werd. 6 priesters werden gevangen genomen en in het kasteel van Bourgondië opgesloten om tenslotte gebonden in de Schelde gegooid te worden. Slechts één priester overleefde.

In 1615 was de klokkentoren aan herstelling toe. De werken werden toegewezen aan Simon de Paepe (1585-1636) uit één der belangrijkste Oudenaardse kunstenaarsfamilies. De robuuste toren werd bekroond met een elegante spits (werken tussen 1615 en 1627).

In de 17de en 18de eeuw werd het meubilair vernieuwd in barok en laatbarokstijl.

Een blikseminslag vernielde in 1804 de spits met een hoogte van 13 meter alsook 2 van de 4 hoektorentjes. De spits werd niet meer in zijn oorspronkelijke staat hersteld maar vervangen door de huidige peperbusspits. In de eerste helft van de 19de eeuw werden nieuwe portalen en een sacristie gebouwd.

Een zeer belangrijke restauratie werd tussen 1889 en 1912 uitgevoerd met vervanging van een deel van het meubilair in neogotische stijl. In 1894 werd de beiaard van het stadhuis naar de kerk overgebracht.

Spijtig genoeg werd in 1918 op het einde van WOI de kerk zwaar toegetakeld zodat een nieuwe ingrijpende restauratie zich opdrong.
Meer over Oudenaarde tijdens en vlak na WOI ...

De kerk bezit een schat aan beeldhouwwerk, houten en stenen polychromiebeeldjes, historische wandtapijten en schilderijen (van o.a. Simon de Pape en Caspar de Craeyer). In de kerk zijn er 14 kapellen die een variatie aan houten en marmeren altaren bevatten. De kapellen zijn opgericht ter ere van een heilige, vaak de patroonheilige van een gilde.

Eeuwenlang stonden kleine huisjes rond de kerk. In 1964 werden deze afgebroken met uitzondering van de twee huisjes nu gekend als de Carillon.
In 1526 kreeg Adriaan Detemmerman de toelating om een houten huisje te bouwen aan de Steenen Man, aan de koormuur van de kerk. Dit zou wel eens het eerste huisje rond de kerk kunnen zijn geweest.