Pierwsze wzmianki o powstaniu świątyni katolickiej w Olsztynku sięgają XIV w. Z tego okresu zachowały się zapiski o wybudowaniu ok. 1350 r. niewielkiego kościoła. Niestety został on przejęty przez protestantów w okresie wielkiej reformacji. Nieliczni zamieszkali w Olsztynku i okolicach katolicy musieli uczęszczać przez wiele lat, na nabożeństwa do Gryźlin. Niewielkiej miejscowości oddalonej o kilka kilometrów, ale leżącej na katolickiej Warmii.
Ten stan trwał aż do roku 1868, kiedy to ksiądz Juliusz Ambroży Albrecht odprawił pierwszą mszę. W 1883 r. biskup warmiński skierował już na stałe do Olsztynka polskiego księdza przybyłego z misji w Finlandii, z konkretnym zamiarem utworzenia parafii. Nowy, i w zasadzie pierwszy od wielu lat proboszcz, ks. Paweł Jedzinek zbudował w ciągu następnych pięciu lat murowany kościół, sfinansowany głównie przez warmińskich katolików. W dniu 26 września 1888 roku biskup Andrzej Thiel dokonał konsekracji świątyni, nadając wezwanie Najświętszego Serca Pana Jezusa i świętego Brunona. W 1895 r. została restytuowana parafia rzymskokatolicka.
Kościół jest budowlą halową wzniesioną w stylu neogotyckim, na planie krzyża. Jest trójnawowy z wielobocznie zamkniętym prezbiterium. Świątynia jest murowana z czerwonej cegły i kryta dachówką ceramiczną. Od strony głównego wejścia znajduje się wysoka wieża zakończona spiczastym dachem. Wyposażenie wewnątrz kościoła jest raczej współczesne. Na szczególną uwagę zasługuje ambona, chrzcielnica, ołtarze i stacje drogi krzyżowej.
Na zewnątrz odnajdziemy bardzo charakterystyczna dla tego regionu, pochodzącą z tego samego okresu, kapliczkę maryjną.