Privită de pe apă, biserica pare aproape un punct de observație deasupra strâmtorii Lillebælt. Hramul Sfântului Nicolae, ocrotitorul marinarilor, se potrivește unui oraș a cărui prosperitate a depins de feriboturi, pescuit și trecerea îngustă dintre Funen și Iutlanda.
Actuala biserică din cărămidă a înlocuit probabil o biserică mai veche din piatră în jurul anului 1200. Edificiul romanic inițial a fost mărit și remodelat în repetate rânduri în stil gotic. Turnul, capelele, navele laterale și pridvorul aparțin unor etape diferite de construcție, astfel încât biserica poate fi citită ca o cronologie în cărămidă.
În interior, dacă biserica este deschisă, caută amvonul renascentist din 1596, altarul baroc și picturile din secolul al XIX-lea ale lui C. W. Eckersberg. Monogramele regale de pe băncile din față amintesc de legătura strânsă cu domeniul Hindsgavl și de numeroșii călători puternici care au trecut prin acest oraș așezat strategic.