Kirken er opført 1868-72 i røde munkesten på en sokkel af granit. Kirken er opført i nyromantisk stil med et nordvendt tårn, der vender mod Holbæks hovedgade. Kirkens hovedindgang er mod nord gennem tårnet. Kirken er opført på samme sted, hvor Klosterkirken, Sct Lucius tidligere lå. Mens klosterkirken dog lå med den traditionelle placering med vestvendt tårn, blev den nyopførte kirke vendt, så tårnet vendte mod nord, formentlig for at give en mere attråværdig adgang fra Ahlgade.
Sankt Nikolai Kirke har gennemgået en omfattende istandsættelse i 1930 samt en knap så omfattende i 1967, ligesom der blev tilføjet to sidefløje langs Kirkestræde til i 1970.
Tårnuret er oprindelig fremstillet til den tidligere Klosterkirke, og uret er forsynet med indskriften "Peter Mathiesen, Copenhagen anno 1737", og uret slår såvel kvarterslag som timeslag.
