The effect of Nb addition in arc-melted CoCrFeNiNbx (0.45 <= x <= 0.65) high entropy alloys (HEAs) on the phase evolution, stability, refinement of the microstructure, and mechanical properties are investigated. Minor fluctuation of Nb modifies the microstructure from hypoeutectic (x = 0.45) to eutectic (x = 0.5) and hypereutectic (x = 0.55) containing 134-200nm thin nanolamellar FCC gamma-Ni and HCP Fe2Nb-type Laves phases. The nano-eutectic CoCrFeNiNb0.5 HEA shows high yield strength (2060 +/- 5 MPa) and strain hardening up to 2200 +/- 10 MPa with 17.0 +/- 0.5% compressive plasticity. Transmission electron microscopic studies of partially deformed specimen has been revealed that the activity of dislocations is present in the eutectic FCC/Laves lamellae and at their interface. The stability of the phases in CoCrFeNiNbx and other eutectic HEAs as reported in the literature, has been assessed by estimating mixing entropy (Delta S-mix), mixing enthalpy (Delta H-mix), atomic size differences (delta), valence electron concentration, Pauling electronegativity (Delta chi(P)), and Allen electronegativity (Delta chi(A)) to predict the evolution and coexistence of eutectic phases.