A község határában kora bronzkori és honfoglaláskori régészeti emléket találtak. Első okleveles említése Nouy névalakban 1275-ből való. 1494-ben Noway, 1546-ban Nowaj, 1648-ban Novaj néven jelölik, míg 1773-tól a ma is használt Novajként nevezik.
Az Egri Püspökség birtokához tartozott. 1430-tól a legújabb időkig az egervári prépostság javadalmának része volt . 1552-ben a törökök felégették, de újra népesült. A kispréposttól 1698 és 1701 között a Buttler család bérelte a birodalmat. Ennek a kornak emlékét őrzi a faluban felállított faragott kemény kőből készült ismeretlen korú úgynevezett török emlékmű.
A török hódoltság megszűntével 1669-ben 9 telekgazdaságból, és 11 zsellérből állt a falu népessége. 1687-ben az Eger visszavételéért folytatott harc során ismét elpusztult. Alig épült fel, a kuruc kor végén 1713-ban és 1722-ben Zorger János egri kisprépost a néptelen Novaj benépesítése érdekében telepítési szerződést adott ki. 1754-ben a javadalom birtokosa, az építtető hajlamú Hubert Mátyás kisprépost. Ekkor a telkes jobbágy- és zsellérháztartások száma 50 volt. Az 1771-i évi úrbér-rendezés során a falu határát első osztályúnak minősítették, s 28 kishold szántóföldet és 8 kaszás rétet mértek ki minden egész jobbágytelekhez. A tagosítást 1865-ben hajtották végre, s ennek során a rétek túlnyomó részét szántóföldben adták a gazdáknak.