Nautrup kirke er en romansk kvaderstenskirke bestående af kor og skib.
Tårnet og det halvrunde våbenhus er bygget i 1931 samtidig med, at kirken gennemgik en meget hårdhændet restaurering (ved arkitekt S. Vig Nielsen, Viborg). Her forsvandt stort set alle spor af oprindelige detaljer. Kirken skal tidligere have haft et tårn, men det var forsvundet før 1750.
Alterbordet er af granit og har i et gemme indeholdt en blykapsel med relikvier. Selve altertavlen stammer fra 1600-tallets begyndelse, mens stafferingen er en smule yngre. Krucifikset i midterfeltet er fra 1931.
Prædikestolen med de fire hjørnesøjler er samtidig med altertavlen. Dydemotiverne i arkadefelterne er dog yngre.
På kirkens nordvæg hænger et epitafium i rokokostil over Alexander Basballe, der var præst i Nautrup, Sæby og Vile 1715-1737. Tavlen blev opsat af hans datter i 1755.
Den lille malmlysekrone, der hænger i skibet, stammer fra 1700-tallet.
I tårnets vestmur har man indmuret en romansk gravsten af granit med et indhugget kors.
Kirkeklokken er antagelig fra første halvdel af 1200-tallet.
I det sydvestre hjørne af kirkegården er der indrettet en slags mindelund med sten fra kirkegårdens nedlagte gravsteder. Af særlige sten kan blandt andet nævnes en stor natursten rejst over Maren og Jens Jensen Grove. Den blev rejst af en taknemmelig giver, som havde fået betalt sin uddannelse af Jens Jensen Grove.
Kilde:
De lokalhistoriske Arkiver i Salling, Fjends og på Fur