Obecna cerkiew wyznawców obrządku greckokatolickiego to dawna kaplica baptystów wybudowana w II połowie XIX w., natomiast po zakończeniu II wojny światowej od 1946 r. przez ponad 30 lat była to świątynia rzymskokatolicka. Obecność społeczności ukraińskiej w Baniach Mazurskich ściśle związana jest z akcją przesiedleńczą przeprowadzoną w 1947 i znana powszechnie jako Akcja „Wisła”.
Początki ich bytności tutaj, również życia duchowego, były bardzo trudne gdyż starano się ich zasymilować całkowicie z nowym otoczeniem czyli oderwać od korzeni. Na początku wierni mogli uczestniczyć wyłącznie na mszy obrządku łacińskiego i dlatego uczęszczali na nią wraz z innymi mieszkańcami. O stopniu restrykcji wobec tej ludności nie świadczy fakt, że gdy podczas sprawowania wspólnych liturgii wielkanocnych w 1954 r. ks. Włodzimierz Boziuk pozwolił wiernym zaśpiewać ukraińskie pieśni religijne, został po tym fakcie przeniesiony do innej parafii.
Mimo, iż w późniejszych latach podczas większych ukraińskich świąt zakazy zelżały, to jednak pierwszy duchowny wyświęcony w obrządku unickim został przydzielony dopiero w roku 1957. W tym również roku 23 kwietnia ks. Jewhenij Usćkyj odprawił pierwszą mszę po ukraińsku i od tego momentu liturgia greckokatolicka zaczęła się odbywać regularnie w każdą niedzielę.
Ten stan rzeczy trwał aż do roku 1975, kiedy to parafia rzymskokatolicka otrzymała w końcu zgodę na odbudowę swojego kościoła zniszczonego pod koniec wojny. Można przyjąć, że od tego roku miejsce to było użytkowane tylko przez grekokatolików, mimo iż nadal pozostawało własnością parafii rzymskokatolickiej. Formalne czyli notarialne przekazanie świątyni na własność parafii greckokatolickiej nastąpiło dopiero 28 listopada 1991 r.
Następne lata to czas remontów i przystosowania cerkwi do wymogów tego obrządku, m.in. ustawiono kopułę na wyremontowanym dachu czy zainstalowano ikonostas wewnątrz niej. Społeczność ukraińska oderwana od swojej tożsamości zyskała w końcu swoje miejsce do integracji i kultywowania swoich duchowych tradycji.
Cerkiew poświęcona św. Mikołajowi znajduje się przy ul. Marii Konopnickiej, głównej drodze prowadzącej do miasta Gołdap.