A falu nevét a Mélóta mondából eredeztetik, melyet Simon Zsigmond Borzova monográfiájában ír le részletesen:
„Az Etelközből megindult magyarok útjukba ejtették Halocsot, melynek ura gazdagon megvendégelte őket. Kezesül, Tuszol leányát Mélótát is a magyarokra bízta, akinek jegyese Borzsova várának ura, Zengor volt. őseink a Kárpátokon átjutva a kezeseket visszaküldték, de időközben Álmos unokája, Béla halálosan beleszeretett Mélótába. A visszatért leányt Zengor nőül vette és Borzsova várába vitte. Béla búslakodott Mélota után és a harcok szünetében kísérőivel a Latorca völgyében kalandozott. Ekkor Zengor fogságába esett. Mélóta otthonában felismerte Bélát, aki bár elszökhetett volna, mégis visszamaradt. Árpád hírét vette Béla esetének és sietve indult, hogy kiszabadítsa. A várat ostromolja, s ekkor Zengor a feleségét kiszökteti a várból, hogy az ostromlók kezébe ne jusson. Rejtekhelye a mai Milota helyén volt. Mikor az asszony értesül, hogy a külső vár már elesett, az ismert rejtekúton visszamegy a várba, hogy Bélát megmentse. Páncélba öltözve a védők közé vegyül. Már a belső várat szorongatják a magyarok, amikor Béla a tornyot felgyújtva kardra kap és megrohanja a várudvaron lévő szláv harcosokat. Véletlenül a páncélba öltözött Mélótával kerül szembe, leszúrja őt, s csak azután ismeri fel, hogy azt ölte meg, akit életénél is jobban szeretett. Bánatában kardjába dől és elemészti magát.”
Nagy Lajos király oklevele tanúskodik arról, hogy a települést 1344-ben a Kölcsey családnak juttatta.
1848-ig Milota jobbágy község volt 92 úrbéres gazdával, mellettük 18 nemesi család is lakott a községben. A falu eredetileg a mai ótemető helyén feküdt, de folytonos árvízveszély miatt az itt élők jobbnak látták, hogy magasabb fekvésű helyre települjenek.
A falu Tiszabecs Nagyközség Közös Tanácsához tartozott, a rendszerváltozás után önálló önkormányzatot alakított. 1990. évi közigazgatási besorolása: Szabolcs-Szatmár-Bereg megyében független polgármesterrel és független képviselő testülettel rendelkező község.