W 1552 roku powstała w Wieliczkach parafia ewangelicka i wkrótce po jej założeniu wybudowano tu pierwszy kościół. Poświęcony został on w grudniu tego samego roku z chwilą objęcia urzędu proboszcza przez pastora Stanisława Rybińskiego. Został on spalony wraz z całą wsią podczas najazdu tatarskiego w 1656 roku. Nie wiadomo jak dokładnie wyglądał, wiadomo natomiast, że był drewniany.
W przeciągu dwóch lat odbudowano go jednak. W drugą niedzielę adwentu 1674 roku zmiótł go wiejący z ogromną siłą huragan (prawdopodobnie wichura zerwała z niego dach i kościół groził zawaleniem więc go rozebrano). Kościół ten również był drewniany, z jego wyposażenia pochodzi ołtarz boczny z 1654 roku znajdujący się w obecnym kościele.
W 1674 roku przystąpiono do kolejnej odbudowy i nowa świątynia stanęła w stanie surowym już w 1676 roku. Postawiono ją wokół starych fundamentów umieszczając pod nią dwie krypty grobowe. Kościół poświęcił arcyprezbiter z Reszla, ówczesny zwierzchnik parafii ewangelickich w 1677 roku. Świątynia ta przetrwała do naszych czasów jako najstarszy drewniany kościół na Warmii i Mazurach (obok świerkowego kościoła w Ostrokole koło Prostek ).
Po II wojnie światowej świątynia została przejęta przez Kościół rzymsko-katolicki, poświęcił ją proboszcz parafii Gąski-Wieliczki ks. Edward Klejno, 11 sierpnia 1946 roku. W 1949 roku rozpoczęto jej gruntowny remont, ponieważ w wyniku działań wojennych groziła zawaleniem. Poprawiono dach, wymieniono podwaliny pod prezbiterium. W 1959 roku zdjęto z dachu dachówkę i zamieniono ją na gont, naprawiono fundamenty i wymieniono niektóre ściany usuwając grzyb. Świątynię oszalowano i odeskowano.
Kościół zlokalizowany jest w samym centrum Wieliczek przy ulicy Lipowej, na wzniesieniu otoczony drzewami. Jest orientowany, jednonawowy z wydzielonym prezbiterium, posadowiony na fundamentach z kamienia łamanego oraz całego nieobrabianego. Ściany świątyni zbudowane są z drewnianych modrzewiowych bali, o konstrukcji wieńcowej. Z zewnątrz budynek okryty jest szalunkiem z desek mocowanych do łat, styki desek kryte są listwami. Zabytkowy wystrój wnętrza świątyni, mimo upływu kilku wieków prawie w ogóle się nie zmienił. Kościół przeszedł wiele remontów, ale nie stracił swojego barokowego uroku.