Muhi környékét a jégkorszakban az év nagy részében hó- és jégréteg borította. Mintegy húszezer esztendővel ezelőtt jelentős változások álltak be Közép-Európa éghajlatában, melynek hatására fokozatosan olvadni kezdett a hó- és jégtakaró. Az alföldi részeken egyre több lett a vízmentes terület. Muhi vidékét füves mezők borították, jelenlegi képétől annyiban különbözött a terület, hogy több volt a víz, mint ma. A Sajó-Hejő folyók közét behálózta a folyóágak, holtágak, erek, mocsarak és ingoványok szövedéke. Akkor még a Szinva patak is ezen a területen bolyongott, majd útja végén beleveszett a Hejőkeresztúr környéki posványos vizekbe.

A falu környékén élő ember nyomait bizonyító ősi leletek a csiszolt kőkorból származnak, mintegy hatezer évvel korábbról. Az újabb kőkori emlékek - a bükki kultúra cserép és eszköz maradványai, és számos Hejőkeresztúri lelet - már egy letelepült emberre utalnak: a kőkor végéről illetve a rézkorból származó cserép és réztárgyak; a rézkori úgynevezett Bádeni kultúra jellegzetes díszítésű agyagedényei; i.e. 1000-500-ból való korai vaskori leletek; az i.e. 500-300-ban megjelent szkíták cserép, bronz és vas eszközei; i.u. II.-IV. századi szarmata leletek; és az i.u. VII.-VIII. századból való avar kultúra tárgyi emlékei. Az ezt követő időkből már okleveles emlékek is fennmaradtak.
Ezek a leletek bizonyítják, hogy Hejőkeresztúr határa mintegy hatezer éve állandóan lakott föld volt. Az előkerült eszközök révén következtetni lehet az itt élt népek kultúrájára, életmódjára. A kőkor végén élt, valamint a vas- és bronzkori ember a földművelés mellett elsősorban halászattal és mellékesen állattartással foglalkozott. Földbe mélyített kunyhókban élt.

Az első név szerint ismert nép a lovas-nomád, harcos keleti szkíta törzsek voltak. I.e. VI. században jöttek hazánk területére és az i.e. III. századig maradtak itt. Keleti kultúrát hoztak magukkal, emellett a síkvidéken tanyáztak és állattenyésztéssel foglalkoztak. Az utánuk érkező szarmaták szintén keletről jöttek, de ok inkább a földművelést részesítették előnyben az állattartással szemben. Azonban a vizek melletti telepeik azt bizonyítják, hogy a halászat fontos létfenntartási tevékenység volt. Az avarok hatalmas harcos, lovas nemzetének jelenléte Borsod megyében több helyen is megállapítható a VII. és VIII. században, Hejőkeresztúrban csak szórványos leleteik tűntek fel, míg a szomszédos Mezőnyéken avar temetőt is feltártak.
Hejőkeresztúr a honfoglalás idején lakott terület volt. Paraszti lakói meghódoltak a kabar törzsek előtt, majd adót is fizettek a borsodi vár ispánjának. A faluról az első évszázadokból nem maradt fenn írott adat. A Keresztúr községnév első írásos említése az úgynevezett pápai tizedlajstromban 1333-ban tűnik fel. Valószínüleg népes falu lehetett, mivel önálló plébániával rendelkezett. 896-1352 között Borsod megye várföldje volt, vagyis állami birtok. Ekkor adományozta Nagy Lajos király a bocsi származású Ónodi Czudar Péternek. 1387-ig magánkézben volt Hejőkeresztúr. Az Ónodi Czudar család ebben az évben megalapította a sajóládi pálos kolostort. Czudar Péter ládi birtokrészét, Czudar György és István Keresztúr nevű falujukat, szederkényi halastavukat, mályi és emődi szőlőiket adományozták a monostor ellátására.
A paraszti lakosság papi és jobbágyi tizedet fizetett és teljesítette a kirótt robotot. A terhek enyhítése végett a barátok elérték Mária királynénál, hogy Mohin és Zsolcán áthaladva ne kelljen út- és hídvámot fizetnie a lakosságnak. Zsigmond király a királyi tisztek bíráskodása alól a barátok tisztviselőinek hatósága alá rendelte a falut. Mivel a világi urak nem szívesen mondtak le jogaikról, ezt a rendelkezést a királyoknak többször is meg kellett ismételniük. A seregvezérek katonai beszállásolásának terhei alól Mátyás király mentesítette Keresztúrt.
A falu a XV. és XVI. században jogilag a pálos barátok birtokában maradt. Azonban a török pusztítás elért idáig is, és 1544-ben Hejőkeresztúr leégett. Ezt a pusztítást a falu még ki tudta heverni. Ezen időben Hejőkeresztúr a töröknek félig behódolt faluja volt, amely adót is fizetett Hatvanba. Azonban az 1596-os török áradatnak a mezőkeresztesi csatavesztés végett Hejőkeresztúr és egész Alsó-Borsod áldozatául esett. A XVII. században Hejőkeresztúr elhagyatott földje beolvadt a Muhi pusztába.
A terület betelepítése csak a kuruc szabadságharcok után indulhatott meg. Az 1596-os pusztulás előtt a falu két részből állott: a templommal rendelkező rész volt Keresztúr, míg a másik felét Noszkádnak nevezték. Az újratelepülés során csak a keresztúri részt népesítették be. A pálos barátok - mint földesurak - elsősorban a Felvidékről hívtak telepeseket. 1730-1740 között érkezett a ruszin telepesek első hulláma. Ezt 1810 után egy újabb csoport követte, sokan a lengyelországi pestis elől menekültek rokonaik után. A ruszinok görög katolikus vallású, szláv nép. 1736-ban a lakosság felét a görög katolikus népesség teszi ki.
1786-ban II. József elkobozta az eltörölt pálos rend vagyonát és átruházta az államra. A jobbágyi kizsákmányolást csak 1848-ban sikerült leráznia a falunak.

CÍMER

A község történetét örökíti meg Hejőkeresztúr címere is. A címer maga egy álló, háromszögletű, kék színű katonai pajzs, amelyet arany hullámpólya oszt két részre. A felső mezőben jobbról élével kifelé, hegyével lefelé forduló ezüst ekevas, balról pedig ezüst kettős kereszt található. Az alsó mezőben jobbra forduló, csőrében kerek kenyeret tartó arany holló látható. A hullámpólya a községnek nevet adó Hejő patakra utal, a kereszt pedig a községnév fő elemére - így a címer úgynevezett beszélő címernek tekinthető. A kereszt pravoszláv jellege a község újratelepítésében részt vevő ruszinokra emlékeztet. Az ekevas a XVIII. századi pecsét ábráját idézi, a holló pedig az itt birtokos pálos rendet.