Sząbruk istniał już w pierwszej połowie XIV w., pierwsza lokacja nastąpiła 22 lipca 1363 r. i nadała została przez Kapitułę Warmińską oraz wójta krajowego Henryka Lutra. Dawna nazwa wsi w języku niemieckim brzmiała Schönbrück co oznaczało Piękny Most, odnosiło się to do przeprawy drogowej która prawdopodobnie istniała między Sząbrukiem i Unieszewem.
Z zachowanych dokumentów wynika, że parafia w Sząbruku istniała jeszcze przed powstaniem tej miejscowości, świątynię uposażono już w wspomnianym przywileju lokacyjnym z 1363 r. Podczas wojen polsko – krzyżackich kościół jak i cała wieś uległ spaleniu, po odbudowaniu 2 kwietnia 1500 r. biskup pomocniczy Jan Wilde konsekrował go ku czci św. Mikołaja i św. Jana Ewangelisty. Pierwotnie była to budowla salowa z zakrystią od północy, w XVII w. dobudowano do niej masywną wieżę ale dopiero w 1790 r. ozdobiono ja hełmem. Obecna forma jest efektem kolejnej rozbudowy przeprowadzonej w latach 1911 – 1913 według projektu Fritza Heitmanna z Królewca.
Do starej zabytkowej nawy dobudowano w układzie prostopadłym trójnawową halę z prezbiterium, w ten sposób stary kościół stał się właściwie przedsionkiem nowego. Ponownej konsekracji dokonał 19 lipca 1913 r. biskup pomocniczy Edward Herrmann, poświecono go również ku czci św. Mikołaja oraz św. Anny. Mimo tak wielu przeróbek kościół zachował wewnątrz całkowicie barokowy wystrój, w tym ołtarz główny z 1774 r. Zachowała się też polichromia na sianach starej części, prawdopodobnie z początku XVI w. a na stropie z XVIII w. Wewnętrzne obejście świątyni otoczone jest kilkumetrowym kamiennym murem oporowym, tworzy to rodzaj arboretum z interesującym doborem roślinnym.
Nierozerwalną częścią tego nietypowego ogrodu są wolnostojące figury wotywne, w narożnikach ogrodzenia od strony głównej drogi wbudowano dwie kapliczki. Kościół usytuowany jest na wzniesieniu przy drodze Gietrzwałd – Tomaszkowo, jego malownicza więc bryła dominuje nad okolicą i jest doskonale widoczna. W roku 1968 obiekt wpisany został do rejestru zabytków.