De in 1342 gestichte kerk was gewijd aan Onze-Lieve-Vrouwe-ter-Sneeuw en werd in 1472 onder Wolfert V van Borselen een kapittelkerk, bestaande uit twintig kanunniken. Naast deze koorheren waren er vijf kapelaans, een Cantor en drie koorzangers aan de parochie verbonden. De nieuwbouw werd vanaf 1479 geleid door de Vlaamse bouwmeester Antoon I Keldermans. Na diens dood in 1512 nam zijn zoon Rombout die taak over.
Na 1520 werden de Heer van Veere en zijn familieleden niet langer in de kapel van kasteel Sandenburgh maar in een grafkelder in de Grote Kerk begraven. De kerk moet tal van graven hebben bevat, waaronder ook dat van de in 1465 gestorven Schotse koningsdochter Maria Stuart, die gehuwd was met Wolfert VI van Borsele en daardoor markiezin van Veere. Priesters werden in een priestergraf in het koor begraven en voor wie genoeg geld bezat werd een graf of een grafkelder onder de vloer van de kerk gereserveerd. De graven waren een belangrijke bron van inkomsten voor de kerk. Voor anderen waren er graven op het kerkhof rond de kerk.
Na 1521 werden alle bouwactiviteiten gestaakt: zodoende kwam het geplande stenen netgewelf niet tot stand: de kerk hield een houten zoldering. De zware, ingebouwde westtoren bleef bij één geleding steken. De kerk werd luisterrijk ingericht en in 1543 door George van Egmont, Bisschop van Utrecht gewijd.
