Eutectic high entropy alloys (EHEAs) hold promising industrial application potential, but how to design EHEA compositions remains challenging. In the present work, a simple and effective strategy by combining mixing enthalpy and constituent binary eutectic compositions was proposed to design EHEA compositions. This strategy was then applied to a series of (CoCrFeNi)Mx (M = Nb, Ta, Zr, Hf) HEAs, leading to the discovery of new EHEAs, namely, CoCrFeNiNb0.45, CoCrFeNiTa0.4, CoCrFeNiZr0.55 and CoCrFeNiHf0.4. The microstructure of these new EHEAs comprised of FCC and Laves phases in the as-cast state. The experimental result shows that this new alloy design strategy can be used to locate new EHEAs effectively.