Pierwszy kościół w Sętalu wymieniany jest w dokumentach pochodzących z roku 1344, niestety brak jednak jakichkolwiek informacji na temat jego wyglądu. Najprawdopodobniej został on zniszczony podczas wojny polsko – krzyżackiej, toczonej w latach 1519-1521. Nowa świątynia została odbudowana w tym samym wieku, 30 października 1583 r. konsekrował ją biskup Marcin Kromer powierzając opiece Wszystkich Świętych i Świętego Mikołaja. Ta budowla przetrwała do roku 1908 kiedy strawił ją pożar, ale już tego samego roku przystąpiono do jej odbudowy według projektu Fritza Heitmanna z Królewca. Prace budowlane zakończone zostały w 1910 r. natomiast 11 lipca 1911 r. ponownej konsekracji nowego obiektu, ale pod dotychczasowym wezwaniem dokonał biskup Augustyn Bludau.
Kościół w Sętalu to budowla orientowana i trójnawowa, utrzymana w stylu neogotyckim. Wzniesiono go z czerwonej cegły na rzucie prostokąta, od zachodu przylega do niego kwadratowa wieża z kruchtą w przyziemiu. Świątynię przykrywa dach dwuspadowy, z którego wyrasta smukła wieża zwieńczona kutym krzyżem. Korpus obiektu został oszkarpowany, a jego ściany podzielone na przęsła przez wmontowanie ostrołukowych okien.
Wyposażenie i wystrój kościoła jest raczej ujednolicone, pochodzi głównie z początku XX wieku i utrzymane jak całość w stylu neogotyckim. Godne uwagi są drewniane rzeźby o różnym wątku religijnym, które ozdabiają ołtarz główny i ołtarze boczne. Zachowały się także cenne zabytki sztuki złotniczej, warto tu wspomnieć o kielichach i naczyniu na oleje święte z wieku XVIII czy pacyfikale wykonanym w tym samych okresie w warsztacie złotnika Jerzego Mittaga w Dobrym Mieście.
Przy kościele zachowały się ślady dawnego cmentarza z ciekawymi przykładami starych żeliwnych krzyży, zachował się także nagrobek jednego z dawnych duchownych tej parafii. W roku 1993 świątynia w Sętalu wpisana została do rejestru zabytków.