Parafia w Klewkach powstała praktycznie równocześnie z powstaniem wsi. Na Warmii, tak jak na całym terenie Prus, powstawanie sieci parafialnej było równoległe z kolonizacją ziem. Klewki otrzymały lokację 13 kwietnia 1352r. z rąk Kapituły Warmińskiej. Majątek został nadany rycerzowi pruskiemu Clauko von Hohenbergowi, jemu też zawdzięczał swoją pierwotną nazwę – Clauki (póxniej Klakedorf, Klauckendorf i ostatecznie – Klewki). Rycerz Clauko otrzymał patronat nad mającym powstać kościołem.
Nie jest obecnie znane nazwisko pierwszego proboszcza parafii. Najwcześniejsze dane dotyczą Christiannusa Laurentiego, który sprawował funkcję proboszcza w latach 1481-1505. Jego następcami byli kolejno: Wawrzyniec Preylhoff (w latach 1505-1524), Jakub Loebbe (1560-1562), Marcin Kokoszka (1563-1570), i Maciej Gadomski (1570-1577). Wiadomości o dwóch ostatnich z wymienionych można znaleźć w testamencie strażnika leśnego Jana Szlungi z 1577r. Z dokumentu tego wynika również, że region warmiński był w owym czasie silnie spolonizowany, a ludność czuła wyraźne przywiązanie do wiary chrześcijańskiej.
W 1577r. parafię przejął ks. Sebastian Rembowski z Janowa. Na urzędzie proboszcza, nadanym przez biskupa Marcina Kromera, pozostał do 1598r. Przejmując parafię zastał murowany, urządzony kościół z dobrym wyposażeniem w paramenty i szaty liturgiczne. Ks. Rembowski korzystał z tzw. agendy oraz nowej części brewiarza warmińskiego i mszału. W tamtym czasie parafia Klewki czerpała dochody z zapisanych jej 5 łanów (84 ha) lekkiej ziemi, dziesięciny w wysokości 6 łasztów zboża (łaszt wynosił 3000-3840 dm3) i innych ofiar, jak 30 kurcząt z kolędy i opłat za posługi religijne i zwyczajowe.
Jak wynika ze sprawozdania powizytacyjnego z 14 stycznia 1598r., ówcześni parafianie byli dobrymi chrześcijanami, wszyscy odbyli spowiedź wielkanocną, jednakże szlachta z Kaborna i Trękusa zbyt rzadko uczęszczała na Msze. Nieczęsto udzielano namaszczenia chorych. Proboszcz przestrzegał wiernych przed nierządem i napominał nauczyciela klewkowskiej szkoły do lepszego wypełniania swoich obowiązków. Z kolei nauczyciel, Andrzej z Chorzeli na Mazowszu, skarżył się na niskie wynagrodzenie, które w dodatku często trudno było wyegzekwować. Uposażenie Andrzeja składało się z 3 groszy za dzwonienie, 9 groszy za pieczenie opłatków, 2 solidów i fury drewna opałowego za posługę od każdego domu i 1/3 kolędy.
W 1607 r. parafię przejął ks. Marcin Matthae z Janowa, ur. w 1573r. Klewkowski majątek należał wówczas od rodziny Rabów. To szlachcic Jerzy Rab wskazując kandydaturę ks. Matthae doprowadził do objęcia przez niego urzędu proboszcza. Ks. Matthae odprawiał Msze w niedziele i święta z Mszału rzymskiego oraz czasem w dni powszednie z ksiąg zwykłych. Przy tłumaczeniu Biblii korzystał z przekładu ks. Wujka, Kazań Piotra Skargi Postylli Echa. Dochody proboszcza pochodziły z 5 łanów ziemi, dziesięciny z wiosek (6 łasztów i 11 korcy zboża) oraz różnych ofiar (25 grzywien w gotówce, 30 par kurcząt, od wigilii 1 grzywna od osoby). Dwóch ogrodników korzystających z plebańskiej ziemi dodawało do tego po 1 grzywnie i 10 groszy oraz po 2 kurczęta.
Świątynia była w tym czasie zadbana i dobrze wyposażona (7 ornatów, 5 alb, 13 obrusów ołtarzowych, 5 welonów do kielicha srebrnego, pozłacanego i drugiego srebrnego, 10 chorągwi, sporo welonów na ołtarz, relikwie świętych Jerzego i Krzysztofa). W stojącej na wschód od kościoła szkole z drewnianych belek nauczał wówczas Jan z Janowa (ok. 40 lat, żonaty), biegły w śpiewie. Zarabiał rocznie około 20 grzywien.
Znaczne zasługi w rozwój parafii wniósł ks. Maciej Orłowski, ur. w 1730r. w Sętalu, który przejął probostwo w Klewkach w 1765 r. Ustanowił on jedyne na Warmii Bractwo św. Walentego, który był już wówczas patronem parafii. Założył też mały szpitalik na osoby (2 kobiety i 2 mężczyzn), z przywilejem nadanym przez biskupa Krasickiego 8 maja 1798r. Księdzu Orłowskiemu pomagał wikariusz Piotr Sadrynna, rodowity Warmiak z dobrą znajomością języka polskiego i niemieckiego. Mieszkał i stołował się z proboszczem, był pracowity i pilny i otrzymywał 22 talary i 20 groszy wyposażenia. Posługę w parafii pełnił również kalikant (wprowadzający w ruch miechy w organach) Grzegorz Aleksiński, wynagradzany 60 groszami rocznie. Nadal działała szkoła w Klewkach, która dzięki ofiarności parafian otrzymała nowy dwuizbowy budynek. Funkcję nauczyciela sprawował wówczas Józef Fromm, ur. w 1766 r. w dekanacie dobromiejskim.
Rocznicę poświęcenia kościoła obchodzono w tamtym czasie zawsze w pierwszą niedzielę po 21 lipca. Dochody parafii pochodziły z 5 łanów ziemi i ogrodu przy domu (uprawianego przez samego proboszcza) oraz dziesięciny (po 149 korcy żyta i owsa, z kolędy od wolnych po 36 groszy, od osadników po 33 grosze, od ogrodników po 2 grosze). Dodatkowe opłaty zgodne z zarządzeniem synodalnym wynosiły 18 groszy za zapisanie do chrztu, od szpitala 4 grosze, od ślubu 18 groszy i za odprowadzenie zwłok 15 groszy. Do tego dochodziły sumy pochodzące z beneficjów (proboszcz otrzymywał określoną kwotę w zamian za zobowiązanie do odprawienia konkretnej liczby Mszy w ciągu roku).
W końcu XVIII w. parafia liczyła 950 wiernych (w tym 615 „zobowiązanych do sakramentów”). Nie praktykowano zabobonów, guseł czy wróżb. Nabożeństwa niedzielne i świąteczne zaczynały się latem o 600, zaś zimą około 800. Msza święta przedpołudniowa zaczynała się nieco po 900. Pokazaniach, głoszonych zawsze po polsku, następowały modlitwy zwykłe, z których ostatnią odmawiano w intencji króla. Do parafii nie należała żadna publiczna kaplica czy klasztor, zaś 25 protestantów uczestniczyło w nabożeństwach w kaplicy w Olsztynie. Z cmentarza, otoczonego parkietem ze sztachet, wydzielono część dla grzebania luteran.
Brakuje źródeł o działaniu parafii w następnych latach, aż do okresu Kulturkampfu. Wiadomo, że wówczas pojawiły się trudności – po śmierci ks. Franciszka Gahblera (proboszcza klewkowskiego w latach 1848-1874) rząd pruski jednocześnie utrudniał mianowanie następcy i ukarał biskupa karą 500 marek za nieobsadzenie parafii. Parafianom służył w tej sytuacji wikariusz z Klebarka Wielkiego ks. Józef Kiszporski. Dopiero w 1883 r. parafia doczekała się nowego proboszcza – ks. Ignacego Jackowskiego. Ten zmarł zaledwie po dwóch latach sprawowania funkcji i został zastąpiony przez ks. Franciszka Quandta.
W XIX w. majątek należał do rodziny Lous, pochodzenia szwedzkiego. Następnie zakupili go von Steinowie, a po nich, w 1905r. Franciszek Otto. Wdowa po Franciszku wyszła za konwertytę, Fryca Klemmę, który był wielkim dobroczyńcą klewkowskiego kościoła. Ostatnim właścicielem majątku był Jan Hoepfner z Płoskini.
W latach (1893-1932) proboszczem był ks. Hieronim Poetsch (ur. 1856). Otaczał on szczególna opieką polskich parafian i często uczestniczył w uroczystościach narodowych w Olsztynie. Aktywnie włączył się do kampanii organizacyjnej i propagandowej w czasie plebiscytu na Warmii i Mazurach, organizował też wiece wyborcze do sejmu pruskiego w latach 1911 i 1913 (wiec w 1911r. odbył się w stodole ks. Poetscha). Alojzy Heide, nauczyciel dawnej szkoły niemieckiej w Klewkach, tak go wspominał: „Był bardzo gorliwym kapłanem, punktualnym, bardzo przystępnym, dla każdego miał zawsze otartą rękę, tak że po śmierci niewiele zostało dla spadkobierców”.
Od 1926r. sędziwemu już ks. Poetschowi pomagał wikariusz Antoni Jascholtowski, po kilku latach przeniesiony do Barczewa, zmarły jako jeniec wojenny w transporcie więźniów między Terespolem a Kazaniem. Kolejnym wikariuszem został ks. Franciszek Klimek urodzony w Gryźlinach. Po śmierci ks. Poetscha do czasu objęcia probostwa przez ks. Leona Kamińskiego nabożeństwa sprawował ks. Paweł Dziendzielewski.
Ks. Kamińskiego, ustanowionego proboszczem Klewek w roku 1932, czekały trudności związane z wojną. W czasie II wony światowej był delegowany przez biskupa Maksymiliana Kallera do pracy wśród Polaków w diecezji chełmińskiej. Jego działalność nie spodobała się hitlerowcom (mimo zakazów słuchał spowiedzi po polsku), za co przez dwa tygodnie był więziony w bydgoskim więzieniu. Po powrocie do Klewek w 1945 r. bez żadnej pomocy od strony diecezji przywracał parafię od normalnego stanu po zniszczeniach wojennych. Odbudował spaloną plebanię, odrestaurował i artystycznie wymalował świątynię. W 1962 r. na własną prośbę odszedł na emeryturę. Parafianie zachowali w swoich sercach taką wdzięczność do ks. Kamińskiego, że w 1994r. ufundowali tablicę pamiątkową poświęconą temu duszpasterzowi.
Po ks. Kamińskim parafię przejął ks. Benedykt Siedlewski. Był przyjacielem ludu polskiego na Warmii, był zainteresowany historią regionu i parafii. Po dwóch latach posługi kapłańskiej w Klewkach został przeniesiony do Mikołajek Pomorskich. W tym samym roku co księdza Siedlewkiego do parafii skierowano również wikariusza ks. Huberta Poschmanna, który jako gorliwy katecheta dojeżdżał z nauką religii do Linowa, Kaborna i Szczęsna.
Kolejnym proboszczem został ks. Stanisław Nowak, który był równocześnie prokuratorem Seminarium Duchownego w Olsztynie. W Klewkach wykazał się szczególną gorliwością w katechizowaniu dzieci i młodzieży szkolnej. W 1976r. przeniesiono go do Wydmin.
Miejsce ks. Nowaka zajął ks. Bogdan Grzankowski, również prokurator Wyższego Seminarium Duchownego „Hosianum” w Olsztynie. Był bardzo zaangażowany w pracę duszpasterską, a parafianie cenili jego ciepło i wyrozumiałość. Zmarł przez upływem roku od objęcia probostwa na wylew krwi do mózgu.
Następca ks. Grzankowskiego został ks. Tadeusz Kask. Nowy proboszcz sam katechizował dzieci i młodzież z Klewek i innych wiosek. Wspierał go w pracy duszpasterskiej wikariusz Aleksander Sieńkowski, w 1982r. przeniesiony na misje. Przez cztery miesiące 1981r. wikariuszem w Klewkach był również ks. Marian Glinkowski, zaś w latach 1982-83 ks. Roman Żółtański. W 1983r. ks. Kask przejął parafię w Jedwabnie, w Klewkach zaś zastąpił go ks. Antoni Faliński, który, podobnie jak ks. Nowak i Grzankowski, pełnił również funkcję prokuratora w olsztyńskim Seminarium.
W 1986r. parafię przejął ks. Krzysztof Lebdowicz. Poza pracą duszpasterską musiał odnaleźć się również jako gospodarz istniejącego na terenie parafii gospodarstwa rolnego stanowiącego zaplecze gospodarcze olsztyńskiego seminarium. W 1989r. jego wysyłki nagrodzono II miejscem w konkursie na wzorową zagrodę. Ks. Lebdowicz był nie tylko proboszczem-gospodarzem, ale i dyrektorem administracyjnym WSD „Hosianum”. Jako proboszcz rozbudował kaplicę w Szczęsnem, która wcześniej mogla pomieścić zaledwie około 5 osób (prawdopodobnie była wówczas miejscem kultu prywatnego). Obecnie kaplica ta bywa wykorzystywana przez mieszkańców Szczęsna jako miejsce odprawiania nabożeństw majowych i październikowych, ponadto w Wielką Sobotę odbywa się w niej święcenie pokarmów. Księdza Lebdowicza wspomagali wikariusze: ks. Andrzej Pluta, duszpasterz młodzieży i rodzin Olsztyna, ks. Zbigniew Ciapała, późniejszy budowniczy kościoła Parafii Trójcy Przenajświętszej w Morągu, oraz ks. Cyryl Klimowicz, obecnie biskup diecezji Świętego Józefa w Irkucku.
Historię parafii spisano w oparciu o książkę Ewy Gołaszewskiej Klewki. Z dziejów kościoła i parafii.