The strengthening effects introduced by the addition of 2 at% titanium, vanadium, and niobium, as the well-known micro-alloying elements, to the model CrMnFeCoNi high-entropy alloy (HEA) were studied in the present work. Accordingly, the microstructure, mechanical properties, and strengthening mechanisms of the as-cast CrMnFeCoNi, (CrMnFeCoNi)98Ti2, (CrMnFeCoNi)98V2, and (CrMnFeCoNi)98Nb2 HEAs were investigated by electron-backscattered diffraction (EBSD), tensile testing, differential scanning calorimetry (DSC) thermal analysis, and theoretical calculations and measurements. Depending on the nature of the added elements and their segregation tendency during solidification, different degrees of microstructural refinement were observed in the as-cast ingots. The segregation tendency of Ti was found to be more pronounced compared to that of V (as predicted by the Scheil-Gulliver model), leading to a more refined secondary dendrite arm spacing (SDAS) and grains (resulting from the growth restriction factor and constitutional undercooling). Moreover, Nb addition led to the formation of the (Cr,Fe,Ni)2(Nb) Laves phase at the last stages via the eutectic solidification. The effect of the Laves intermetallic compound (type C14) and twinning-induced plasticity (TWIP) effect on the strength-ductility synergy was discussed. Moreover, a detailed modeling of the strengthening mechanisms revealed that the grain boundary strengthening (represented by the Hall-Petch relationship) and solid solution hardening (due to the lattice distortion) were the primary contributors to the increase in yield strength of V- and Ti-containing HEAs. On the other hand, the formation of the Laves phase, besides solid solution and grain boundary strengthening mechanisms, could lead to a considerable increase in the yield strength of the Nb-containing sample; although it would deteriorate the ductility of the alloy, as also discussed based on its brittle fracture surface appearance and the presence of micro-cracks. Accordingly, the present study is applicable to the design of modified Cantor-based HEAs.