A templom a XIX. század első évtizedében épült, tornyát 1814-ben emelték. Egyszerű, késő barokk teremtemplom, a hajóba beugró homlokzati toronnyal. Főoltára késő barokk munka a XVIII. század második feléből.

Az 1734. évi összeírás szerint a falu régi katolikus templomát a reformátusok használták. A katolikus egyház újjászervezését Barkóczy püspök 1749-ben kezdeményezte, de a refomátusok ezt megakadályozták. 1767-ben veszprémi László olaszliszkai plébános adományából Czikó Mihály helyi katolikus földesúr kápolnát építtetett, így Ezsterházy püspök Újfehértót önálló plébániává nyilvánította.Első plébánosa Sasvári Antal volt. 1776-ban a kápolna összedőlt. Három évtizedig a szentmiséket a Czikó kúria egyik szobájában tartották. Új templom építéséhez-Aurer Pál debreceni építésszel-1804-ben kezdtek, és a templomot 1812. nov.26-án szentelték fel Mindenszentek tiszteletére. 1901-ben Burgfeld Ferenc egri mester egy manuálos, 8 regiszteres orgonát készített a templomnak. A templom titulusa 1990 óta Magyarok Nagyasszonya. A torony csak 1814-ben készült el. A plébániaház, melyet Czikó Mihály földesúr építtetett 1771-ben, 1843-ra lakhatatlanná vált. Újat 1846-48-ban építettek. A templomot utoljára 2001-ben renoválták. A liturgikus teret 1973-ban alakították ki, Gondos István plébános idejében. A közel 150 éves plébánia épületet utoljára 1999-ben renoválták. Egy kőkereszt áll a templomnál, kettő a temetőben, egy a nyíregyházi úton. A templomkertben, 1962-ben létesített lourdes-i barlang található.