Parohija u Nadalju je osnovana 1801, iste godine kada je osnovano i selo. Ali knjige krštenih i umrlih vođene su od 1756, a venčanih od 1795. godine, još dok su prvi naseljenici pustare Nadalj bili stanovnici Čeba (Čelareva). Te knjige su prenete u Nadalj i dalje ovde vođene, kako je zabeležio u Letopisu Srpske pravoslavne crkve u Nadalju njen prvi paroh Teodor Georgijević (Toša Đorđević). Isti podaci nalaze se i u Izveštaju Šajkaškog bataljona od 30. marta 1803. godine podnetom Ministarstvu rata u Beču. Prema tom izveštaju, u Nadalju je već 1801. godine podignuta mala crkva od naboja i pokrivena trskom. Improvizovan je i mali oltar. U toj crkvi bogosluženje je držano samo godinu dana, dok nije podignuta zgrada škole. Tada je oltar prenet u školu koja je istovremeno služila i kao crkva sve do 1813. godine, dok nije završena sadašnja pravoslavna crkva od tvrdog materijala.
Gradnja sadašnje pravoslavne crkve u Nadalju započela je 12/24. aprila 1811. godine, a završena 15/27. avgusta 1813. godine, kako je zabeleženo na svodu crkve gde se oltar deli od soleje. Crkvu je osvetio žabaljski prota Sava Berkić na dan Svetog apostola Andrije Prvozvanog 30. novembra/12. decembra 1813. godine, uz činodejstvo više sveštenika i prisustvo brojnih meštana i gostiju. Crkvena slava je Ivandan (Rođenje Svetog Jovana Krstitelja), 7. jula po novom kalendaru. Prema Veljku Petroviću, ikonostas crkve izradio je Jeftimije Popović. Dužina zgrade je 27 metara, širina 9, visina zidova 10, a visina tornja bez krova je 30 metara.
Apila 1849. godine, posle bitke kod Sentomaša, Nadaljčani su u panici pobegli iz sela koje je tada spaljeno. Tada je izgorela i crkva: oltar, stolovi, prozori, krov i gornji deo tornja. Posle uspostavljenog mira, izbeglice su se vratile u opostošeno selo. Pred crkvom su našli sagorele delove ikonostasa. Crkva je odmah očišćena, umesto ikonostasa bilo je zastrto platno, a nešto kasnije postavljena je daščana oltarska pregrada sa nekoliko ikona.
Maja 1850. godine, car Franc Jozef je odobrio za obnovu postradalih crkava na području tadašnjeg Vojvodstva Srbije i Tamiškog Banata sumu od 500.000 forinti. Posebne komisije su procenjivale štetu u svakom mestu. Pravoslavne crkve u Šajkaškoj dobile su 82.883 forinte i 9 novčića srebra. Šteta u Nadalju je procenjena na 12.266 forinti, a samo šteta na crkvi iznosila je 7.678 forinti. Za obnovu crkve dobijena je suma od 6.868 srebrnih forinti. Pomoć pravoslavnim crkvama u Šajkaškoj stigla je i iz Rusije. Nadaljska crkva je dobila nekoliko vrednih knjiga među kojima i Psaltir štampan još 1783. godine u Sanktpeterburgu.
Pedesetih godina 19. veka podignut je nov krov i drveni toranj sa satom. Sadašnji zidani toranj završen je 1880. godine i postavljen je novi sat. Porta i krst na sredini sela bili su ograđeni letvama sa zidanim stubovima, a 1885. godine postavljena je ograda pred crkvom koja i danas stoji. Deo ograde ispred Svetosavskog doma postavljen je 1914. godine.
Godine 1887. godine velika oluja je teško oštetila krov crkve pa je Crkveni odbor odlučio da proda tri jutra zemlje i izvrši opravku. Dve godine kasnije, za istu svrhu, dobijeno je od države 150 forinti.
Prema prvom Izveštaju Eparhije Bačke od 1893, nadaljska crkva je „iznutra dobro”, ali spoljašnja opravka još nije bila dovršena. Crkvena opština je tada posedovala još jednu zgradu koju je ustupila u najam školi, zatim tri jutra zemlje (ostavština Luke Petrova), kao i skromnu gotovinu u novcu. Godine 1900. crkva je posedovala i parohijsku sesiju od 35 jutara zemlje u nadaljskom ataru.
Godine 1906. obnovljen je krov crkve postavljanjem eternit-ploča. Iste godine je izvršena pozlata jabuke i krsta na vrhu tornja.
Marta 1910. godine Opštinsko poglavarstvo u Nadalju ustupilo je Crkvenoj opštini 50.000 kruna za popravku crkve. Istog meseca na sednici Upravnog odbora Crkvene opštine konstatovano je da su šajkaške političke opštine dobile u posed oko 40.000 jutara rita čime im se materijalno stanje bitno popravilo. Stoga je Crkvena opština u Nadalju očekivala od političke opštine obimniju pomoć za popravku crkve, odavno teško oštećene u međusobnoj borbi (1848/49) „dva zavađena bratska naroda koji su kroz tolike vekove zajednički protiv nekrsta vojevali.” Svakako je to bilo u vezi sa pripremom za obeležavanje stogodišnjice nadaljske crkve (1913). Stoga se Crkvena opština na više strana obratila za pomoć napominjući da je prošlo više od 60 godina otkako je crkva teško stradala (1849) i da još nije u stanju u kakvom je bila pre stradanja. Po odobrenju županijskih vlasti, Opštinsko poglavarstvo je 1910. godine izdvojilo još 12.000 kruna, ali za sve veroispovesti u Nadalju, osim za nazarensku jer ova nije bila zakonski priznata. Međutim, uskoro su počeli balkanski ratovi, a posle njih i Prvi svetski rat, pa je obnova crkve ostavljena za bolja vremena. Ali kako su već bila prikupljena znatna sredstva, otkupljena je kuća koja je srušena i na tom mestu podignut je Svetosavski dom (1913-1916).
Za vreme Prvog svetskog rata, kada je Austro-Ugarska počela trpeti poraze na frontovima, sa mnogih crkava u Vojvodini skinuta su zvona i pretopljena u topove. Sa nadaljske crkve skinuta su tri zvona, a jedno je ostalo. „Novac za odneta zvona šrimljen je i to 4100 kruna”, kako piše u zapisniku Crkvene opštine.
Posle rata, kada su se prilike sredile, odlučeno je da se izvrši opšta obnova crkve. Ali i pored jednodušne želje da se izrada ikonostasa poveri akademskom slikaru Jovanu Kešanskom, rođenom u Nadalju, Eparhijski upravni odbor je odlučio da se mora raspisati konkurs, a izrada poveriti slikaru koji ponudi najpovoljnije uslove. Nadaljčani se nisu razumevali u slikarstvo, ali se nisu kolebali u izboru slikara. Na vanrednoj skupštini Crkvene opštine ponovo je doneta jednodušna odluka da se izrada ikonostasa poveri „našem sinu Bati Kešanskom“, ili se odustaje od izrade ikonostasa! Paroh Vojislav Kovačević i predsednik Crkene opštine Milan Rakić delegirani su da Eparhijskom upravnom odboru objasne ovu odluku. Posle dužeg natezanja izrada ikonostasa je poverena Jovanu Kešanskom uz obavezu da prethodno dobro razgleda „moleraj” Saborne crkve i Kapele u Patrijaršijskom dvoru u Sremskim Karlovcima i po tom uzoru uradi svoje u nadaljskoj crkvi. Pune dve godine (1924-1926) trajala je obnova crkve sa izradom novog ikonostasa. Za to vreme bogosluženje je održavano u Svetosavskom domu. Juna 1925. godine podignuta su i osvećena sva četiri zvona koja su i danas na nadaljskoj crkvi.
Uoči Ivandana 1926. godine, obnovljenu crkvu je osvetio Episkop bački Irinej (Ćirić) uz činodejstvo osam sveštenika. Sutradan, na dan crkvene slave, održana je svečana arhijerejska liturgija sa ophodom oko hrama uz prisustvo mnogobrojnih meštana i gostiju. Posle toga, episkop je primio predstavnike „mesne samouprave i korporacije”: Crkvene opštine, političke opštine, Srpskog crkvenog pevačkog društva, Učiteljskog zbora, Udruženja dobrovoljaca, Zemljoradničke zadruge, Agrarne zajednice, Zanatlijskog udruženja i Srpske čitaonice. Posle ovog prijema, episkop je posetio osam kuća u selu: predsednika crkvene i političke opštine, beležnika, najstarijeg učitelja, dve imućne i jednu siromašnu kuću, kao i kuću jedne bogomoljke.
Posle Drugog svetskog rata stručnjaci Pokrajinskog zavoda za zaštitu spomenika kulture Vojvodine u nekoliko mahova posetili su Nadalj i evidentirali vredne objekte. Što se tiče crkve, dali su opis ikonostasa i popisali stare knjige po mestu i godini izdanja:
- Psaltir, Sankpeterburg 1783.
- Minej (opšti), Moskva 1796.
- Služebnik, Budim 1825.
- Služebnik, Beograd 1838.
- Molebni trebnik, Moskva 1848.
- Psaltir (veliki), Moskva 1848.
- Služebnik, Beč 1854.
- Pentikostar, Beč 1885.
Apostol (veliki), Kijev 1881. godine
(Izvor: dr Lazar Rakić, Nadalj (do 1945. godine), Matica srpska, Novi Sad 1988, str.275-286)
