Formiranjem novog naselja Novi Jankovci nakon 1745. godine i konačnog razgraničenja između Granice i Provincijala (civilni cio Hrvatske i Slavonije), to naselje je u crkvenom teritorijalnom ustrojstvu pripalo župi Stari Jankovci koja je potpunu samostalnost stekla 1750. godine. U samom početku postojanja sela ono nije imalo svoju crkvu. U vizitaciji iz 1754. godine se navodi: "Filijala Novi Jankovci, udaljena od župe četvrt sata hoda, bez ikakve je crkve."

Crkveni vizitator je 14. VIII. 1782. godine prvi puta registrirao postojanje drvene crkve posvećene Sv. Andriji koja je imala kapacitet za 80 osoba. Točnu je godinu gradnje teško utvrditi osim da je izgrađena u periodu između 1754. i 1782. godine. Zidana crkva u Novim Jankovcima kakvu danas poznajemo i na današnjem položaju je izgrađena u razdoblju između 1782. i 1811. godine. Naime, crkveni vizitator je 19.VII. 1811. godine zapisao da se u selu nalazi zidana crkva veličine 8 x 3 orgije ili hvata. Očigledno da je i ona bila posvećena Sv. Andriji, jer je imala drveni oltar sa slikom Sv. Andrije obješene s lijeve strane sakristanskih vrata. Sakristija je bila veličine 1,5 x 1,5 orgija ili hvati. Imala je zidani toranj sa 2 zvona težine od 300 i 200 libara. Crkva je kasnije dobila novu posvetu i sada je crkva Svih Svetih. Crkva je nakon privremene okupacije Novih Jankovaca i progonstva hrvatskog i drugog nesrpskog stanovništva potpuno devastirana. Nakon povratka prognanika 1997. godine crkva je obnovljena. Sada katolici Novih Jankovaca mogu opet normalno obavljati sve vjerske obrede u svojoj crkvi.