Wieś Różynka, jej niemiecka nazwa to Rosengarth, założona została w 1359 roku, jej założycielem był wójt krajowy Brunon Luter, a lokalizację potwierdził biskup warmiński Jan Stryprock. Miejscowość została całkowicie zniszczona w latach 1519-1521 podczas wojny polsko-krzyżackiej.
Nie ma żadnego potwierdzonego dokumentu odnośnie powstania pierwszego kościoła, przypuszcza się tylko, że powstał on prawdopodobnie w XIV w. Istniejąca świątynia została wybudowana w 1604 r., a konsekrowana 26 listopada 1606 r. i poświęcona ku czci św. Mateusza Apostoła. Kościół zbudowano w stylu późnogotyckim, jest murowany, na rzucie prostokąta, orientowany. Posiada wydzielone, trójbocznie zamknięte prezbiterium, dobudowane wtórnie. Drewniana wieża, na rzucie kwadratu, szalowana i konstrukcji słupowej, postawiona została w XVIII w., natomiast jej obecny dach wykonano w 1935 r. gdy poprzedni uległ spaleniu. W 1912 r. dobudowano do kościoła nowe prezbiterium z zakrystią oraz kruchtą.
Wyposażenie wnętrza jest dość skromne, na uwagę zasługuje późno klasycystyczny ołtarz główny z barokowym tabernakulum, dwa barokowe ołtarze boczne jak również ambona. Natomiast podobnie jak w większości takich miejscowości ciekawym elementem jest stary cmentarz przykościelny. Liczne niemieckie groby posiadają pięknie kute krzyże, jakże typowe dla takich nekropolii i okresu. Obok okalającego kościół i cmentarz płotu znajduje się obelisk, wyryte na nim nazwiska upamiętniają mieszkańców Różynki i okolic poległych podczas I wojny światowej.