Kościół w Nakomiadach nie występował w spisie parafii lub kościołów filialnych parafii diecezji warmińskiej przed 1525 rokiem. Jednak w zapisie lokacyjnym wsi były 4 łany na utrzymanie kościoła. Pierwsza wzmianka o kościele w Nakomiadach pochodzi z 1554 roku i to pw. św. Antoniego. Takiego patrona kościoła nie wybrali protestanci. Kościół w Nakomiadach najprawdopodobniej obsługiwał krzyżacki kapelan zamku w Rynie. Kapelan ten obsługiwał też kaplicę św. Wawrzyńca w Rynie. Z obsługą duszpasterską w Nakomiadach, podobnie jak w Wilkowie, chodziło o to, aby dziesięcina trafiała do kapelana, a nie do diecezjalnego proboszcza. Samodzielna parafia protestancka powstała w Nakomiadach w 1556 r. W 1880 na terenie parafii było 1882 mieszkańców (w tym 1552 luteran). W roku tym urodziło się 59 dzieci, zmarły 54 osoby i zawarto 8 małżeństw.

     W 1932 r. kościół w Nakomiadach przeszedł gruntowny remont. Dobudowano wówczas wieżę (wcześniej była wolno stojąca dzwonnica drewniana). Kościół powiększony też został o kruchtę i zakrystię. Wewnątrz kościoła przesunięto XVII-wieczny ołtarz w ten sposób, że opiera się o ścianę. Kiedyś za ołtarzem było zejście do krypty pod kościołem. Według miejscowych podań z kościelnych podziemi prowadził tunel do dawnego zameczku krzyżackiego.
Od 1980 r. kościół użytkują katolicy. Świątynia otrzymała nowego patrona – św. Józefa.

Przed kościołem znajduje się pomnik parafian poległych w I wojnie światowej z następującą inskrypcją: „Zum Andenken • den im • Weltkriege Gefallenen • 1914-1918 20”.