The existence of an HCP phase in FCC-type high-entropy alloys can improve the alloy’s mechanical properties. In many cases, an HCP phase is induced by deformation. In the present work, an FCC to HCP transition was detected during the cooling of Co1.5CrFeMnNi0.5 and Co1.75CrFeMnNi0.25 alloys. Therefore, arc-melted annealed CoxCrFeMnNi2−x (x = 0.25–1.75) alloys that were then subjected to long-term vacuuming were investigated using XRD, DSC, HT-XRD, thermodynamic calculation, and first-principle calculation. It was confirmed that the FCC to HCP transition occurred at ~450 °C during the cooling of the alloys with x ≥ 1.5. The volume fraction of the HCP phase increased with Co content. It was proven that the HCP phase was not stable above 600 °C. First-principle calculations further indicated that the HCP structure was more stable than the FCC structure for Co1.75CrFeMnNi0.25 alloy, and there was a likelihood of an FCC to HCP transition. Moreover, experimental tests confirmed that the microhardness of the Co1.75CrFeMnNi0.25 alloy reached 213 HV because it contained a substantial HCP phase. This value is much higher than those of other non-HCP-containing alloys, either in their as-cast states or after annealing. These results provide guidance for the design of FCC-type high-entropy alloys with desirable mechanical properties through HCP phase strengthening.