O pierwszym kościele w Sętalu, z pewnością drewnianym, nie zachowały się żadne wzmianki. Następny kościół, również drewniany, był konsekrowany 30 października 1583 roku przez biskupa Marcina Kromera i otrzymał wezwanie Wszystkich Świętych i Świętego Mikołaja. Istniał do roku 1908, kiedy to spłonął w niewyjaśnionych okolicznościach. W następstwie pożaru zaginęła, pochodząca z 1595 roku, monstrancja. Podejrzewano, iż uległa zniszczeniu w ogniu. Do czasu, gdy w roku 1931 pojawiła się niespodziewanie na aukcji w szwajcarskiej Lucernie. Mimo starań władz kościelnych diecezji warmińskiej, nie udało się monstrancji odzyskać, ale pojawienie się jej w nienaruszonym stanie wzbudziło wiele pytań dotyczących przyczyn pożaru sętalskiego kościoła.

Mieszkańcy Sętala szybko wybudowali nową świątynię – pracami kierował ówczesny proboszcz ksiądz Andreas Bajinski. Autorem projektu był Fritz Heitmann – architekt z Królewca. W latach 1908-1910 powstał ceglany, trzynawowy kościół w stylu neogotyckim, z wydzielonym czworobocznym prezbiterium, ze strzelistą 52 metrową wieżą (w jej górnej części umieszczono mechanizm zegarowy), częściowo włączoną w bryłę świątyni oraz boczną kruchtą. Nad głównym wejściem do kościoła, umieszczonym w bryle wieży, znajduje się mozaika przedstawiająca Chrystusa Dobrego Pasterza.

Wyposażenie kościoła, pochodzące z początku XX wieku, jest jednolite. W ołtarzu głównym uwagę zwraca grupa rzeźb przedstawiająca Trójcę Przenajświętszą – Bóg Ojciec podtrzymuje krzyż z umęczonym Chrystusem, a nad nimi jest gołębica – symbol Ducha Świętego. Po obu stronach przedstawienia są płaskorzeźby ukazujące sceny z życia Jezusa – cud w Kanie Galilejskiej i cudowne rozmnożenie chleba i ryb. W zwieńczeniu ołtarza głównego rzeźbiona postać św. Mikołaja – patrona świątyni.

Na końcu naw bocznych również znajdują się ołtarze. W lewej nawie znajduje się w nim przedstawienie Matki Bożej Różańcowej i św. Dominika oraz figury świętych: Anny i Joachima – dziadków Pana Jezusa. W prawym bocznym ołtarzu znajduje się płaskorzeźba przedstawiająca Przemienienie Pańskie oraz figury św. Walentego i Bartłomieja. Ambonę zdobią drewniane figury Jezusa i czterech ewangelistów – szczególną uwagę zwracają tutaj znajdujące się przy nich ich symboliczne przedstawienia.

Organy znajdujące się nad głównym wejściem do kościoła wykonał Vitalis Stange z Braniewa, zaś autentyczne witraże z 1910 roku, przedstawiające postacie świętych, pochodzą w pracowni w Trewirze. Padające przez nie światło, w połączeniu granitowymi kolumnami podtrzymującymi sklepienie i pięknym neogotyckim wyposażeniem, nadaje wnętrzu kościoła atmosferę mistycyzmu oraz skłania do modlitwy bądź zadumy.