Obecność Ukraińców nie tylko w okolicach Kruklanek ale także na terenie Północnej Warmii i Mazurach to pokłosie akcji przesiedleńczej „Wisła” przeprowadzonej w roku 1947. Głównym celem tej akcji było osłabienie grup nacjonalistycznych działających na Ukrainie zabierając zaplecze życzliwej im społeczności. Wskutek tych działań przesiedlono około 58 tysięcy Ukraińców zarówno wyznania greckokatolickiego jak i prawosławnych. Pośrednim punktem tej akcji była asymilacja Ukraińców z nowym otoczeniem które miało doprowadzić do wykorzenienia własnej tożsamości. Niestety ukrócenie struktury wyznaniowej było jedną z metod nacisku, dlatego jeśli nawet nie zakazano przynależności do Cerkwi greckokatolickiej, to zdecydowanie zabronione było odprawianie mszy św. w tym rycie. Do 1956 r. wyznawcy wywodzący się z grupy przesiedleńczej korzystali z kościołów rzymskokatolickich i szafarzy tego obrządku. W tymże jednak roku władze wyraziły zgodę odprawianie mszy w rodzimym języku ale nadal w kościołach rzymskokatolickich. Był to okres wielu kontrowersji i konfliktów nawet ze strony duchownych.
Msze greckokatolickie w kościele w Kruklankach zaczęto odprawiać w 1962 roku i rok ten uznaje się za datę powstania parafii dla tej ludności. Mimo to szanse na własną świątynię pojawiły się dopiero na początku lat 90–tych ubiegłego wieku. Kamień węgielny pod budowę cerkwi greckokatolickiej wmurowano w 1996 r. Budowę rozpoczęto w 1998 r. a jej symboliczne zakończenie nastąpiło 25 grudnia 1999 r. kiedy odprawiono pierwsze nabożeństwo. Poświęcenie tej świątyni, powierzające ją opiece świętego Jozafata Kuncewicza, nastąpiło jednak dopiero 14 września 2002 r. Szafarzem tej ceremonii był ks. abp Jan Martyniak.
Obecnie jest to samodzielna jednostka obejmująca nie tylko Kruklanki ale i wiele ościennych miejscowości. Sam obiekt, projektu Bohdana Boberskiego z Warszawy, jest na wskroś nowoczesny i swym wyglądem przypomina typowe współczesne kościoły. Godny uwagi jest współczesny ikonostas przy ołtarzu głównym. Na zewnątrz warto chwilę zatrzymać się przy pamiątkowym głazie upamiętniającym akcję przesiedleńczą - dość częsty element na tym terenie.
Cerkiew mieści się przy ulicy Wodnej.