Luteranie mieszkali na terenie Żuław od XVI w., niemal od początku budowali także swoje świątynie. Pierwszy dom modlitwy w Nowej Cerkwi powstał ok. 1619 r. Niszczony przez powodzie i wojny zawsze był odbudowywany. Ostatni powstał w 1838 r., była to dwudziestometrowa szachulcowa konstrukcja zwieńczona niewielką wieżą.
Po 1945 r., gdy niemal wszyscy luteranie opuścili te tereny. Kościół przez jakiś czas był pod opieką miejscowej parafii katolickiej (która jednak miała własną świątynię), w 1951 r. przejęty został przez miejscowy PGR na magazyn. Budynek pozbawiono charakteru sakralnego (m.in. rozebrano wieżę) i wykorzystywano tak do lat siedemdziesiątych. Porzucony popadał w ruinę.
W 1989 r. powstał pomysł rozebrania budynku i przeniesienia go w inne miejsce. Po dokonaniu inwentaryzacji świątynię rozebrano i odtworzono (90% elementów drewnianych trzeba było wykonać na nowo) w Elblągu. Na nowo poświęcona służy parafii katolickiej na Zatorzu. W Nowej Cerkwi pozostał plac ze stertą kamieni (zapewne będących dawną podmurówką) informacyjną tabliczką.