Het imposante kerkgebouw, waarvan iedereen zich afvraagt hoe het in zo’n klein stadje kan staan, heeft een geschiedenis die teruggaat tot de dertiende eeuw, tot kort na de stichting van Brouwershaven in 1285 door Floris V. Bij de restauratie van 1956-1962 zijn veel nieuwe gegevens gevonden over de kerk en haar dienaren. Zo werd duidelijk dat de koster in 1323 van de Graaf van Holland het schrijfambt kreeg.
De oorspronkelijke uit circa 1325 daterende, 11 meter brede, eenbeukige kerk met een vijfhoekig gesloten koor, was gewijd aan Petrus en Paulus. In 1540 werd de kerk gewijd aan de H. Nicolaas, de patroon van de zeevarenden.
Begin 15e eeuw werd begonnen met de bouw van een transept en koor met kapellen en kooromgang. Het koor vertoont de overgang van Vlaams- naar Brabants gerichte gotiek. De ronde zuilen zijn versierd met voorlopers van de Brabantse koolbladkapitelen. In het eerste kwart van de 16e eeuw begon de vervanging van het eenbeukige schip door het huidige halleschip, waarbij de oorspronkelijke kap opnieuw is toegepast. Het houten gewelf rust op gesneden figuren, zogenaamde schalkbeeldjes. De twee houten figuurtjes verbeelden Nicolas en Jacobus Major, de schutspatronen van de zeelieden. De hooggeplaatste beeldjes zijn waarschijnlijk aan de beeldenstormers ontsnapt! In 1573 kwam de kerk in protestantse handen.
De kerk werd vergroot met de zuiderzijbeuk en omstreeks 1540 kwam de noorderzijbeuk tot stand; de voltooiing met de midden en zuidbeuk vond een kwart eeuw later plaats. In dezelfde tijd vond ook de aanbouw van de sacristie en van een weer verdwenen doopkapel tegen de westgevel van de zuidbeuk plaats. Ook werden toen de zuid- en westportalen gebouwd. Een deurtje leidt naar het broodhuisje met een mooi kruisgewelf en een beschildering. Hier werd het brood aan de armen uitgedeeld. Later werd er een grote schouw gebouwd, waarin tot 1953! de kolen voor de voetstoofjes warmgestookt werden.
Tegen de westmuur plaatste men in 1557 het orgel van Hendrik Niehoff, waarvan de kas nog origineel is. De roze kleur heeft men teruggevonden in een oude verflaag, maar dateert volgens de huidige inzichten uit de 18e eeuw. Omdat het aantal parochianen laag bleef, was niet alleen de bouw in fasen noodzakelijk maar moest men ook allerlei extra belastingen heffen, zoals op haring en bier. Zelfs het leveren van stenen voor de bouw van de kerk kon als een straf voor een overtreding worden opgelegd.
De tekeningen van restauratiearchitect Lussanet de la Sablonière, belast met de restauratie van 1956-1962, geven een goede indruk van de verschillende bouwfasen vanaf 1325 tot het tweede kwart van de 16e eeuw.
De huidige kerkruimte is 82,50 meter lang, 28,50 meter breed en 24,90 meter hoog. Het portaal onder het orgel was vroeger de hoofdingang. De akoestiek van het kerkgebouw is bijzonder goed.
Omdat de kerk zwaar beschadigd was door de watersnoodramp van 1953 was opnieuw een restauratie noodzakelijk. Maar helaas, na de voltooiing van in 1963, was wederom een restauratie nodig: de bekapping bleek ernstig aangetast door de bonte knaagkever. Na een driejaar durende restauratie (1991-1994) werd de kerk na ingebruikname vereerd met een bezoek van koningin Beatrix.
De nu zeer sobere, ruimtelijke hallenkerk moet in de katholieke tijd een rijk interieur hebben gehad met zijaltaren van de vele gilden. Aan de zuilen hingen in die tijd de gildenborden. De Gilden namen daarnaast ook ieder het onderhoud van een kerkraam op zich. De twee grootste glazen, links en rechts van het orgel, werden in 1836 bij een storm verwoest en niet hersteld maar dichtgemetseld.De huidige ramen zijn uit de 19e eeuw.
De vloer van de kerk bevond zich als gevolg van de inwerking van zout na de watersnoodramp van 1953 in een slechte staat. In 2004 en in de eerste maanden van 2007 werd de vloer in twee fasen geheel gerestaureerd. De kerk werd met deze opgeknapte vloer op 12 mei 2007 feestelijk in gebruik genomen en is nu weer goed toegankelijk, ook voor hen die slecht ter been zijn.
Toren
De eerste toren van de kerk stamt uit 1667 en herbergde drie klokken. De toren werd vernieuwd in 1734, in de Franse tijd afgebroken en in 1883 weer herbouwd.
In 1932 werd de toren vergroot, omdat er geen plaats was voor de grootste van de beide klokken. De kleine klok is een Mariaklokje uit 1510. Jan van Borssele schonk in 1604 de grote klok. Op deze klok staan de wapens van de familie Van Borssele, het wapen van de provincie Zeeland en het wapen van de stad Brouwershaven. De mallen van de wapens zijn te bewonderen aan de noordzijde in het koor.
Consistoriekamer
Een fraaie eiken deur, met beslag en kruisboog, leidt naar de consistoriekamer. Deze dateert uit het midden van de 16e eeuw. Hier ziet men een prachtig netgewelf en een schouw met tegeltjes en een gesneden eiken kap uit 1650. In de consistoriekamer bevindt zich een rijke inventaris: enkele 17e-eeuwse stoelen, een antieke kist en een oud archiefkastje. Van 1982 tot en met voorjaar 2006 werd deze kamer door de Hervormde gemeente gebruikt als winterkerk omdat in de kerk verwarming ontbreekt.