Pierwsze wzmianki o kościele parafialnym w Nowej Cerkwi pojawiają się w 1653 roku w dokumentach wizytacyjnych. Przeczytać tam możemy o kończącej się budowie świątyni, która była wznoszona z drewna w miejsce podobnego, niedawno spalonego budynku.

Kolejny kościół parafialny wzniesiono w Nowej Cerkwi przed rokiem 1744, a jego patronami byli św. Maria Magdalena i św. Andrzej Apostoł.

W 1763 r. Budynek poddano gruntownej odnowie dzięki staraniom ówczesnego proboszcza ks. Marcina Borcka. Kościół ten przetrwał do początków XIX w., kiedy to został rozebrany i zastąpiony nową budowlą.

W 1805 r. ukończono budowę nowego kościoła parafialnego. Budynek nie był już drewniany, lecz z tak zwanego "muru pruskiego". Pokryto go dębowym gontem. Istniał on jeszcze ok. 100 lat, bowiem w latach 1911-1913 zbudowano w stylu neobarokowym obecną świątynię parafialną.