We investigated the recrystallization behavior of a cold-rolled CoCrCuFeNi high-entropy alloy (HEA). Two different face-centered cubic phases having different chemical compositions and lattice constants in the as-cast specimen have different chemical compositions: One phase was the Cu-lean matrix and the other was the Cu-rich second phase. The second phase remained even after a heat treatment at 1373 K (1100 °C) and Cu enriched more in the Cu-rich second phase. The calculated mixing enthalpies of both Cu-lean and Cu-rich phases in the as-cast and heat-treated specimens explained that Cu partitioning during the heat treatment decreased the mixing enthalpy in both phases. In the specimens 90 pct cold rolled and annealed at 923 K, 973 K, and 1073 K (650 °C, 700 °C, and 800 °C), recrystallization proceeded with increasing the annealing temperature, and ultrafine recrystallized grains with grain sizes around 1 μm could be obtained. The microhardness tended to decrease with increasing the fraction recrystallized, but it was found that the microhardness values of partially recrystallized specimens were much higher than those expected by a simple rule of mixture between the initial and cold-rolled specimens. The reason for the higher hardness was discussed based on the ultrafine grain size, sluggish diffusion expected in HEAs, and two-phase structure in the CoCrCuFeNi alloy.