Nauteyrarkirkja er í Vatnsfjarðarprestakalli í Ísafjarðarprófastsdæmi. Kirkjan var reist árið 1885, þegar 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á.