Istorija Nove Crnje počinje dolaskom porodice Čekonjić na ove prostore. Tokom kolonizacije, koja je započeta 1792. godine, porodice koje su želele da se nasele u novo selo, morale su se prijaviti feudalcu. U periodu od 25. aprila 1792. do 25. aprila 1805. godine baron je doselio 11 porodica. Međutim, zbog sve češćih poplava veliki broj meštana je napustio selo 1816. godine.
Na mapi Janoša Lipskija (Lipszky János) iz 1808. godine Nova Crnja još uvek nije obeležena kao naselje, nego pored imena Mađar Cernja (Magyar-Czernya, Nova Crnja) piše i pustara Bozitova (Bozitó). Pravi razvoj naselja započet je 1824. godine, kada je nakon smrti svog oca, Janoš Čekonjić postao gospodar imanja Žombolj, a samim tim i Nove Crnje.
Nakon što je 1828. godine baronska porodica raspustila mađarsku koloniju u Česteregu i započela naseljavanje nemačkih porodica iz Žombolja na njihovo mesto, Mađari su se odselili na susednu pustaru Bozitovu. Tada je došlo do ponovnog premeravanja ulične mreže sela, te je Nova Crnja dobila ortogonalnu strukturu.
Antal Bodor (Bodor Antal) u svojoj knjizi s početka 20. veka nastanak sela vezuje za period između 1824. i 1829. godine, što se verovatno odnosi na pomenuti drugi talas naseljavanja. U knjizi Lajoša Nađa (Nagy Lajos) iz 1829. godine Nova Crnja se pominje kao naselje od 1 000 stanovnika. Po ostavinskom materijalu Janoša Čekonjića feudalska porodica je u selu posedovala samo krčmu.
U drugoj polovini 19. veka brojne prirodne nepogode su zahvatile teritoriju imanja, pa i Novu Crnju. Smenjivale su se poplave i suše, što je prilično otežavalo život stanovništva. Čekonjići su prilikom neplodne 1863. godine pokušavali da raznim darovima ublaže bedu svojih podanika. Učestale obilne poplave, koje su zahvatile posed između 1869. i 1872. godine, primoravale su meštane da između naselja saobraćaju čamcima.
Zahvaljujući grofu, 1910. godine je krčma, koja je bila u njegovom vlasništvu, pretvorena u školu. Ovo je bio poslednji dobrotvorni čin feudalske porodice za Novu Crnju. Po ostavinskom materijalu Endrea Čekonjića iz 1932–1933. godine, on je posedovao sledeću imovinu u ovom selu: teritorije ispred i iza crkve i opštinske kuće, kao i njihove bašte, kuće pod brojem 135, 136, 1239/2 i 1240/1 sa dvorištem i vrtom i još nekoliko dvorišta i vrtova unutar naselja.
Uprkos burnoj istoriji 20. veka, Nova Crnja je sačuvala duh kolonizacionih sela iz 19. veka i sećanje na porodicu Čekonjić, mada još uvek okruženo misterijom.
