Nadalj se prvi put spominje u pisanim izvorima 1543. godine kao obveznik prireza. U isto vreme i u istom spisku, spominje se i naselje Nadaš, takođe kao obveznik prireza.
Prvi Nadalj, preteča današnjeg Nadalja, nalazio se pored desne obale Velikog bačkog kanala i druma Turija – Bačko Gradište. U Vojnoj granici, koja je osnovana 1701. godine, Nadalj je u početku vojnički pripadao Čurugu, a od 1809. sa Gospođincima čini zajedničku kompaniju.
U Rakocijevoj buni, koja je trajala od 1703. do 1711. godine, uništeni su i prvi Nadalj (verovatno sredinom oktobra 1705. godine) i naselje Nadaš. Naime, kad je Mađarska oslobođena od Turaka Karlovačkim mirom 1699. godine, nije dobila očekivanu nezavisnost, već je postala deo Habzburške monarhije sa sedištem u Beču. Ferenc Rakoci podiže ustanak za oslobađanje Mađara od austrijske vlasti i nekoliko puta poziva na svoju stranu i Srbe, ali se oni nisu hteli pobuniti protiv cara od kojeg su dobili „privilegije” i države u koju su tek izbegli od Turaka. Austrijski car je tada koristio i Srbe za gušenje ovog ustanka, zbog čega su Rakocijevi vojnici izvršili odmazdu nad srpskim stanovništvom. Iz izveštaja jednog generala Rakociju, saznajemo da je njegova „vojska sve do petrovaradinskih šančeva posekla sve Srbe i sva mesta i svo blago u prah pretvorila.” Većina Srba je bila raspoređena duže reke Tise spremna za sukob sa Turcima koji su još držali Banat, pa nisu očekivali da će ih iza leđa napasti Rakocijeva vojska. Tako su Nadalj i Nadaš pretvoreni u pustare na kojima se posle 100 godina podigao sadašnji Nadalj.
U proleće 1800. godine udaren je kolac na sredini budućeg naselja. Naseljavanje kmetova na pustaru Nadalj odobreno je 19. septembra 1801. godine. Već iste godine podeljeni su placevi i počela je izgradnja kuća.
Srpska pravoslavna crkva posvećena Ivandanu – Rođenju Svetog Jovana, proroka, preteče i Krstitelja Gospodnjeg, sagrađena je u centru naselja 1813. godine.
Za razliku od Srbobrana i Turije, koji su od 1753. do 1848. godine bili u sastavu Potiskog krunskog dištrikta, Nadalj je od svog osnivanja 1801. godine pripao Šajkaškom bataljonu koji je formiran 1763, a ukinut 1873. godine, kao deo Vojne granice. Šajkaši su bili specifičan rod habzburške vojske, koji se kretao u uskim, dugačkim brodovima, poznatim kao šajke. Šajkaši su postojali mnogo pre formiranja Šajkaškog bataljona. Ove vojne jedinice su operisale na Dunavu, Tisi, Savi i Morišu. Učestvovali su u mnogim bitkama protiv Osmanlija, a njihovo učešće je bilo od velike važnosti, jer su bili poznati kao hrabri i vešti ratnici.
U borbama 1848/49. učestvovali su i stanovnici Nadalja. Posle pada Srbobrna 3. aprila 1849. godine, stanovnici Nadalja su izbegli u Titel i Srem. Mađarska vojska je 13. aprila 1849. godine Nadalj upalila, pa je naselje, sem dve kuće, potpuno izgorelo.
Godine 1852, Šajkaški bataljon je transformisan u Titelski pešadijski bataljon. Ova vojna jedinica je ukinuta 1873. godine, a njeno područje tada dolazi pod civilnu vlast i biva priključeno Bačko-Bodroškoj županiji, baš kao i Srbobran i Turija.
Pošta postoji od 1891. godina, a telefon je uveden 1913. godine.
Biblioteka je u Nadalju osnovana 1910. godine.
U Prvom svetskom ratu, vojni obveznici iz Nadalja su 26. jula 1914. godine mobilisani u austrougarsku vojsku. Ne želeći da služe tuđinu, bežali su i skrivali se kao tzv. „logoši”. Na ruskom ratištu su se predavali i prijavljivali u Jugoslovensku diviziju i učestvovali u borbama na Dobrudži i Solunskom frontu. Kroz Nadalj je 16. novembra 1918. godine prošla oficirska konjička patrola srpske vojske, a 20. novembra 1918. godine došla je stalna desetina pešaka. U Prvom svetskom ratu su poginula 94 stanovnika Nadalja.
Između dva rata, Nadalj je opština u srezu Stari Bečej.
Okupatorska mađarska fašistička vojska je ušla u Nadalj 13. aprila 1941. godine. U toku Drugog svetskog rata, slobodoljubivi Nadaljčani pomažu i aktivno učestvuju u narodnooslobodilačkom pokretu. Na stubu i mermernoj ploči u samom centru naselja uklesana su 69 imena stanovnika Nadalja, koji su u toku Drugog svetskog rata izgubili živote. Kao uspomena na poslednje dane borbe za oslobođenje zemlje, na zgradu Zadružnog doma u centru naselja postavljen je deo avionskog krila na kome je zapisano: „Sa ovog aerodroma su početkom 1945. godine izvršavali ratne zadatke 422 jurišni i 112 lovački puk.”
Nadalj je od mađarske fašističke okupacije oslobođen istog dana kad i Turija, 22. oktobra 1944. godine.
Najznačajnija ličnost rodom iz Nadalja je arhitekta Momčilo Tapavica (1862-1949) koji je u prvim obnovljenim olimpijskim igrama u Atini osvojio bronzanu medalju u tenisu i iako se takmičio za Ugarsku, postao je prvi Srbin osvajač olimpijske medalje.
(Izvori:
dr Radoslav Subić, Opština Srbobran – geografska monografija, Novi Sad, 1981.
dr Lazar Rakić, Nadalj (do 1945. godine), Novi Sad: Matica srpska, 1988.)
