Jelentős régészeti leletek bizonyítják, hogy a térség már a bronzkorban is lakott volt. A honfoglaló magyarokat megelőzően szkíták, kelták, szarmaták és avarok lakták a vidéket. A terület a honfoglaló Bors vezér családi szállásföldjéhez tartozott.

A város két település egyesülésből (Nyék és Ládháza) jött létre. Mezőnyék a honfoglaló Nyék törzsről kapta a nevét. Első okleveles említése a XIII. század végéből származik. A település az évszázadok folyamán több névváltozáson is átesett, a Mezőnyék elnevezést csak a XIV. századtól használják. A sok névváltozás annak a jele, hogy a történelem során a tatárok, és a törökök is többször felégették és elnéptelenedett, de mindannyiszor újra benépesült. Ládháza neve a Lád személy- vagy nemzetségnévből ered. Első említése a 1416-ból származik. A történelem viharaiban ez is többször elnéptelenedett, mígnem 1770 körül Miskolc város református családokkal telepítette be. Ekkor indult gyors fejlődésnek. Mindkét település fő bevétele a földművelésből, gyümölcs- és szőlőtermesztésből származott.

1917-ben Mezőnyéki Kavicsbánya néven indult be Közép-Európa legnagyobb kavicsbányája. A kavicsbányászat megnövekedett termelésének következtében a település határában 750 hektáros vízfelület alakult ki. Ezeken a tavakon ma kiváló lehetőség nyílik a vizi sportokra és a horgászatra. 1932-ben a két falu Nyékládháza néven egyesült. 2003-ban városi rangot kapott.