CrFe2NiMnV0.25C0.075 and CrFe2NiMnV0.25C0.125 high-entropy alloys (HEA) were processed by high-pressure torsion (HPT) followed by post-deformation annealing (PDA) at 823 and 1273 K. This severe plastic deformation led to a significant microhardness increment (by a factor of similar to 2.5) up to similar to 435 Hv and the microstructures exhibited exceptional grain refinement with average grain sizes of similar to 30 nm in both HEAs. It was found that the hardness increased up to similar to 555 Hv after annealing at 823 K due to precipitation of the sigma phase, but thereafter the hardness decreased to similar to 195 Hv after annealing at 1273 K which was very close to the value of the initial coarse-grained condition. This behavior is caused by a combination of grain coarsening and a dissolution of the precipitates. These results suggest that the nanocrystalline HEA facilitates the formation of precipitates owing to the large number of grain boundaries which serve both as fast diffusion pathways and as preferential nucleation sites for precipitate formation.