Gradnja sadašnje pravoslavne crkve u Nadalju započela je aprila 1811, a završena avgusta 1813, kako je zabeleženo na svodu crkve gde se oltar deli od soleje. Crkvu je osvetio žabaljski prota Sava Bekrić na dan Svetog apostola Andrije Prvozvanog 30. novembra 1813, uz činodejstvo više sveštenika i prisustvo brojnih meštana i gostiju. Crkvena slava je Ivanjdan (Jovan Preteča), 7.jula po novom kalendaru. Prema Veljku Petroviću, ikonostas crkve izradio je Jeftimije Popović. Dužina zgrade je 27 metara, a širina 9, visina zidova 10, a visina tornja bez krova je 30 metara. Apila 1849, 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. car Franja Josif 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. u Sanktpeterburgu. Pedesetih godina 19. veka podignut je nov krov i drveni toranj sa satom. Sadašnji zidani toranj završen je 1880. i postavljen je novi sat. Porta i krst na sredini sela bili su ograđeni letvama sa zidanim stubovima, a 1885. postavljena je ograda pred crkvom koja i danas stoji. Deo ograde ispred svetosavskog doma postavljen je 1914. godine. Godine 1887. 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. 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 mnogim crkvama u Vojvodini skinuta su zvona i pretopljena u topove. Sa nadaljske crkve skinuta su tri zvona, a jedno je ostalo. 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 Patrijaškom 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. podignuta su i osvećena sva četiri zvona koja su i danas na nadaljskoj crkvi. 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
Lazar Rakić „Nadalj“, 1988.