Zanim jednak powstał obecny kościół, w drugiej połowie XIV wieku ówcześni mieszkańcy wybudowali w tym miejscu kościół drewniany. Spłonął on prawdopodobnie podczas jednego z licznych w tym czasie grabieżczych najazdów litewskich. Kolejny, już ceglany, wzniesiono w połowie XVI wieku. Biskup Marcin Kromer konsekrował go w 1580 roku. I tą świątynią mieszkańcy długo się nie cieszyli – spaliła się już na początku XVII wieku. Kościół został odbudowany po pożarze i konsekrowany w 1619 roku przez biskupa Rudnickiego. Dotrwał aż do II połowy XIX wieku. Był już wtedy jednak zbyt mały, aby pomieścić wszystkich parafian.

Ówczesny proboszcz, ksiądz Franciszek Kaupowicz, rozbudował kościół. Jednak nie rozwiązało to problemu braku miejsc, więc w latach 1865-1867 przeprowadził zbiórkę pieniędzy z myślą o budowie nowej świątyni. Kiedy w kościele zaczęły już pękać ściany boczne i osuwać się fundamenty, kolejny proboszcz, ksiądz Herman Macherzyński, podjął po roku 1890 decyzję o rozpoczęciu prac budowlanych. Nie dane mu było jednak zobaczyć nowego kościoła – zmarł w 1893 roku i budowę dokończył jego następca – ksiądz Walenty Barczewski.

Autorem projektu brąswałdzkiej świątyni był architekt Fritz Heitmann z Królewca. Specjalizował się on w projektowaniu neogotyckich miejskich kościołów. W zamyśle budowniczych taki miał być właśnie kościół w Brąswałdzie – monumentalny, trzynawowy z wysokim sklepieniem oraz ze strzelistą, wysuniętą z bryły budynku wieżą w części zachodniej i wydzielonym prezbiterium od wschodu (kościół jest orientowany). Powstał w latach 1894-1896. Uroczystej konsekracji dokonał biskup warmiński Andrzej Thiel w 1897 roku, nadając mu wezwanie św. Katarzyny. Wymowne jest tutaj malowidło znajdujące się na północnej ścianie prezbiterium. Ukazuje symboliczne przeniesienie ciała św. Katarzyny Aleksandryjskiej ze starego kościoła do nowego. Dzięki temu zachowany został dla potomnych wizerunek dawnej świątyni (znajduje się w lewej górnej części malowidła).

Księdzu Walentemu Barczewskiemu zawdzięczamy w kościele nie tylko freski o treści patriotyczno-historycznej, ale również obecne wyposażenie. Neogotycki ołtarz główny został wykonany w Regensburgu. Znajduje się na nim płaskorzeźba Chrystusa niosącego krzyż oraz druga – przedstawiająca Jego zdjęcie z krzyża. Na górze figura Chrystusa Zmartwychwstałego. Do ołtarza w południowej nawie ksiądz Walenty Barczewski zakupił obraz Trójcy Świętej fundacji biskupa warmińskiego Andrzeja Szembeka. Nawę północną zdobi ołtarz z wizerunkiem Matki Bożej Ubogiej i dwiema rzeźbami: św. Barbary i św. Marii Magdaleny. Na szczególną uwagę zasługują dwa duże obrazy umieszczone po obydwu stronach bocznego wyjścia z kościoła – przedstawiają one Zwiastowanie i Ukrzyżowanie.