Hejőkeresztúr települése valószínüleg azzal a Noszkád nevü községgel azonosítható, amely már a XIII. század elején létezett. A Noszkad elnevezés eredetét tekintve a Noszkod személynévból származhat. A szokások szerint a legtöbb helységet személyekről nevezték el, így eredete a XI. század végére, XII. század elejére tehető. A XIII. századból már határai is ismeretesek: Muhi felőli Heyew (Hejő) melletti fövenyes keletről, Hosszúverem (Hwzyverem) gázló, Kengyelér (Kengeler), Telekérfog völgy ( Thelukerfoka), Forrod víz, az Emődről Muhiba vezető országút. A XIV. században már a Noszkadkeresztúr elnevezés is előfordul. A Keresztúr helynév arra vall, hogy a falu templomát a Szent Kereszt tiszteletére avatták. Az Árpád-kori szokás szerint ugyanis nem csak a szenteket urazták, hanem a megfeszített Jézus keresztfáját is. Így a község létrejötte a templom felépítésének idejére tehető - valamikor az Árpád-kor vége felé. 1904-ben már hivatalosan is Hejőkeresztúr néven van bejegyezve.