Miejscowość została założona najpierw jako wieś w 1346 roku na miejscu wcześniejszej osady pruskiej. W dniu 30 kwietnia 1385 roku miasto lokował biskup warmiński Henryk Sorbom. W przywileju kolacyjnym uposażono kościół parafialny. Pierwotnie kościół farny w Bisztynku miał posiadać godność Świętej Marty, ale biskup Sorbom zmienił tytuł przy konsekracji kościoła na św. Macieja Apostoła.
W czasie mszy konsekracyjnej podczas podniesienia Hostii miały upaść na ołtarz krople krwi. Od tamtych czasów świątynia jest traktowana jako sanktuarium Krwi Chrystusa. Nasilony od początku XVIII wieku ruch pielgrzymkowy spowodował konieczność powiększenia świątyni. Najpierw w roku 1739 z fundacji biskupa Krzysztofa Andrzeja Jana Szembeka dostawiono północną nawę boczną, a jej konsekracji 4 sierpnia 1748 roku dokonał biskup Adam Stanisław Grabowski.
W 1798 roku do parafii należały miejscowości: Bisztynek, Troszkowo, Dąbrowa, Kokoszewo i folwark Sękity. W parafii istniała również szkoła parafialna. Po pożarze z 1770 roku dobudowano nawę południową, całość przedłużono o trzy przęsła w kierunku wschodnim i ujednolicono elewację budowli. Bardziej ozdobny wygląd otrzymała jedynie fasada kościoła, którą zaprojektował miejscowy architekt Ernest Mazur. Świątynię konsekrował 5 sierpnia 1781 roku biskup Karol Hohenzollern w obecności biskupa Ignacego Krasickiego.
Obecnie świątynia jest trójnawową halą o ośmiu przęsłach w stylu późnego baroku. Ołtarz główny jest w stylu rokokowym, a wykonany został przez Chrystiana Bernarda Schmidta z Reszla. Dziełem tego samego artysty są ołtarze boczne kończące nawę południową i północną oraz ołtarze boczne przy czwartej parze filarów. W kościele znajduje się gotycka rzeźba Madonny z Dzieciątkiem z II połowy XIV wieku. W ścianie północnej kościoła znajduje się kamienna tablica z herbem biskupa Szembeka z datą 1739. Z obrazów w kościele na uwagę zasługuje portret Ignacego Krasickiego oraz dziewięć obrazów Apostołów. Ozdobą obejścia kościelnego są rzeźby postaci naturalnej wielkości dwunastu Apostołów ustawione na otaczającym kościół murze.
