A település neve egy 1234-ben kelt, de később átírt oklevélben szerepel először. Az 1332-es tizedjegyzékben Homefalu néven szerepel, mint plébániás község. Hosszú időn át az Abák birtoka volt. Neve már 1352-ben megegyezett a maival.
Halmaj címere egy álló, háromszögletű, vörös színű katonai pajzs két ezüst pólyával; a pajzsot egy csaknem teljes kört formázó arany hal díszíti. A pajzs zöld színű halomra támaszkodik. A pajzstartók – amelyek ugyancsak a halmon állanak – két fekete és arany színű griff; ezek egyik-egyik mellső lábukkal színes toll-legyezőket emelnek oromdísz gyanánt a pajzs fölé.
A címer értelmezése: A két ezüst pólyával díszített vörös pajzs a régi Abaúj vármegye címere, a község területi hovatartozására utal. A hal a község régi pecsétjének az ábrája, az ezen pecsétábrától eltérő elhelyezése a pajzson címeresztétikai szempontból indokolt. A címertartók: a fekete-arany griffek a községről nevezett Halmaji Bor család középkori címeréből valók. A címer, és címertartók alapja, a zöld színű halom utalás a község nevére.
