Från vattnet ser kyrkan nästan ut som en utsiktsplats över Lilla Bält. Att den är helgad åt Sankt Nikolaus, sjömännens skyddshelgon, passar en stad vars välstånd byggde på färjor, fiske och det smala sundet mellan Fyn och Jylland.
Dagens tegelkyrka ersatte troligen en äldre stenkyrka omkring år 1200. Det som började i romansk stil byggdes ut och omformades flera gånger i gotisk stil. Tornet, kapellen, sidoskeppen och vapenhuset tillhör olika byggnadsetapper, så kyrkan kan läsas som en tidslinje i tegel.
Om kyrkan är öppen kan du leta efter renässanspredikstolen från 1596, barockaltaret och C. W. Eckersbergs målningar från 1800-talet. Kungliga monogram på de främsta bänkarna minner om det nära förhållandet till Hindsgavl och de många mäktiga resenärer som passerade denna strategiskt belägna stad.