Nauteyrarkirkja er í Vatnsfjarðarprestakalli í Ísafjarðarprófastsdæmi.  Kirkjan var reist árið 1885, þegar sóknarkirkjan var flutt til Nauteyrar frá Kirkjubóli í Langadal, þar sem hún hafði staðið öldum saman.

Á Kirkjubóli er enn þá grafreitur.  Kirkjusmiður var Jón Halldórsson á Laugabóli.  Kirkjan er úr timbri, bárujárnsklædd.  Hún er veglegt hús og tekur hátt á annað hundrað manns í sæti.  Setloft er í henni.

Af merkum gripum hennar má nefna fornan kaleik frá 1750, gerðan af Sigurði Þorsteinssyni, silfursmiði í Kaupmannahöfn.  Vegna þunns jarðvegs á Nauteyri eru grafir grunnar og leiðin há.