Muiden is een van de oudste nederzettingen van ons land, er wordt al over Muiden gesproken in een oorkonde uit het jaar 953. De eerste kerk in Muiden zal vermoedelijk van hout geweest zijn en is gesticht door de H. Liudger. Van deze kerk is door de komst van plunderende Vikingen niets meer over. Omstreeks 1150 werd een tufstenen kerk in Romaanse stijl gebouwd met een 28 meter hoge toren. De toren van deze kerk staat nog altijd overeind. De kerk zelf werd omstreeks 1425 in groter formaat en gotische stijl herbouwd. De kerk is toegewijd aan de H. Nicolaas en is lang door de katholieke gemeenschap in Muiden gebruikt.
In 1581 vond de ‘alteratie’ plaats: de roomsen werden vervangen door aanhangers van de nieuwe religie. De St. Nicolaaskerk werd overgenomen en het St. Catharinaklooster voor nonnen opgeheven. De katholieken hadden het zwaar te verduren. Aan het eind van de 80-jarige oorlog in 1648, werden de katholieken weer getolereerd en kwamen ze bijeen in een schuilkerk. Deze stond lange tijd in de Naarderstraat. In het begin van de 19e eeuw is dit gebouw in een slechte staat en te klein geworden voor de gemeenschap. Vanaf 1795 mogen de Roomse armen van het Armbestuur ook meedelen in de opbrengsten van de armenbussen. Met de groeiende katholieke gemeenschap ligt het voor de hand dat er nu weer een echte kerk voor de katholieken kan komen. Rijkswaterstaat zorgt voor het ontwerp van T.F. Suys en de uitvoering hiervan. In 1825 is de bouw van de waterstaatskerk aan de Herengracht voltooid.
De Statie Muiden werd in 1858 verheven tot een parochie, die zichzelf mag besturen. Zo ontstond de H. Nicolaasparochie voor Muiden en Muiderberg. De kerk en de parochie zijn toegewijd aan de H. Nicolaas en de H. Catharina. Het kerkgebouw werd in 1894 uitgebreid met een nieuw priesterkoor. In 1900 kreeg de H. Nicolaasparochie zijn eigen R.K. begraafplaats in Muiden. De kerk is sinds 4 juni 1973 een rijksmonument.
De H. Nicolaasparochie is op 1 januari 2012 gefuseerd met de H. Laurentiusparochie uit Weesp en verder gegaan als de Parochie van Levend Water toegewijd aan de H. Laurentius en de H. Nicolaas. De H. Nicolaaskerk aan de Herengracht in Muiden doet vandaag de dag nog steeds dienst.