De voorm. (Herv.) O.L.-Vrouwekerk (Oudestraat 26) is een forse, in natuursteen uitgevoerde, driebeukige basilikale kruiskerk met driezijdig gesloten koor, dito zuiderzijkoor en een onafgebouwde toren van twee geledingen met haakse steunberen, twee traptorens en een koepeldak. In 1332 werd op deze plek begonnen met een kerk die in 1348 werd verheven tot parochiekerk, gewijd aan O.L. Vrouwe ter Sneeuw. Delen van het koor kunnen uit die tijd dateren. In de loop van de 15de eeuw werd dit koor vergroot tot een driebeukig hallenkoor (waarvan twee beuken resteren). Omstreeks 1470 werd aan de kerk een kapittel verbonden. Mogelijk onder leiding van Evert Spoorwater begon men aan de uitvoering van een ambitieus bouwplan in laat-gotische stijl. Het werk kwam in 1479 onder leiding van Anthonis Keldermans en in 1512 van diens zoon Rombout. De slechts gedeeltelijk voltooide toren bereikte in 1520 de huidige hoogte. Het driebeukige schip met de kapellen aan beide zijden en het transept met de forse opengewerkte dakruiter werden waarschijnlijk tussen 1500 en 1520 voltooid. Aan de oostzijde van het transept bevinden zich twee veelhoekige traptorens en een sacristie. Gebrek aan voldoende financiële middelen verhinderden de bouw van een groots opgezet koor en men beperkte zich tot de verbetering van het bestaande, iets uit de as van de rest van het gebouw staande, hallenkoor door aan de oostzijde van het middenkoor een provisorische kooromgang te maken (gereed 1543).
Na de Reformatie in 1572 werd het middenschip als protestantse kerk in gebruik genomen en het transept als wandelkerk. Het noordkoor diende vanaf 1614 als Schotse kerk. In 1686 brandden schip en transept uit, waarbij de gewelven en de dakruiter verloren gingen. Bij het herstel verdwenen de topgevels van het transept en kreeg de toren zijn huidige bekroning. Midden- en zuidkoor - bekend als de Kleine Kerk - werden in 1686 ingericht als Waalse en Lutherse kerk en dienden vanaf 1800 als Hervormde kerk; het noordkoor werd van 1800 tot de afbraak in 1832 als Lutherse kerk gebruikt. In 1809 leed het gebouw schade bij beschietingen door de Engelsen. In 1811 richtten de Fransen het schip en transept in als militair hospitaal, waartoe vier houten verdiepingsvloeren werden ingebracht en de ramen werden uitgebroken en ingevuld met metselwerk en kleine vensters. Na de Franse tijd is het gebouw ook nog als provinciaal bedelaarsgesticht en opnieuw als hospitaal in gebruik geweest. Rond 1900 zijn de verdiepingsvloeren weer verwijderd. Na een lange periode van leegstand heeft men de kerk als cultureel centrum ingericht na de restauratie in de jaren tachtig van de 20ste eeuw. De Kleine Kerk is in 1950 gerestaureerd.
Inwendig hebben schip en transept ronde zuilen met koolbladkapitelen. De zijbeuken en de kapellen waren met kruisribgewelven gedekt; de voor de hoofdbeuk en het transept ontworpen stergewelven zijn nooit uitgevoerd. Het triforium, nog aanwezig in het transept, bestaat uit een balustrade gevat in de doorgetrokken raamnissen. Tot de inventaris van de Kleine Kerk behoort voornamelijk 17de-eeuws meubilair, waaronder een preekstoel, doophek, herenbank en twee lezenaars. Het grafmonument met obelisk voor Jan van Miggrode († 1627), pastoor en later predikant te Veere, is in 1771-'72 vervaardigd door Heinrich Schweitzer met brokstukken van de oorspronkelijke grafzerk. Het in 1855 door H.D. Lindsen voor de R.K. kerk te Sassenheim gebouwde orgel werd - na een verblijf in Middelburg - in 1928 te Veere geplaatst.
Het kerkhof is in 1834 gesloten. De ringmuur rond het kerkterrein dateert van 1813. Aansluitend op de gemetselde hekpijlers van de toegang tot het terrein staat de voorm. portierswoning (Oudestraat 28) uit circa 1813. Vlakbij de kerk bevindt zich een waterput met cisterne (Oudestraat ong.). In deze in 1541-'43 mede voor de Schotse wolhandelaren gebouwde cisterne werd via loden pijpen onder de straat het water van het kerkdak opgevangen. Mogelijk naar ontwerp van Keldermans werd de put in 1551 overdekt door een laat-gotisch achtzijdig natuurstenen gebouw met tentdak en een straalgewelf met natuurstenen ribben. Aan één van de drie gesloten zijden is het wapen van Veere aangebracht. De vijf open zijden hebben Tudorbogen op slanke zuilen. In 1968 en 2000 is het bouwwerk gerestaureerd.
