The behavior and the mechanism of fatigue crack propagation in CrCoNi medium-entropy alloys (MEAs) with heterogeneous microstructures were investigated in this paper. After cold-rolling and recrystallization annealing at different temperatures and times, five sets of heterostructured specimens were acquired with different recrystallization levels. Then, the structure characterizations of these five sets of specimens were carried out by nanoindentation testing and electron back-scatter diffraction (EBSD) mapping. Finally, the fatigue crack propagation tests were conducted on single edge crack specimens of these different heterogeneous microstructures. The experimental results indicate that the crack propagation rates of specimens with partial recrystallization microstructures are higher than those with complete recrystallization microstructures, and the effect on fatigue crack thresholds of these specimens is the opposite. The fatigue cracks grow along the slip planes or twin boundaries in recrystallization grains (RGs), which induced crack deflections and the roughness-induced crack closure effect. For this reason, the area percentage of recrystallization and the grain size of RGs have a great effect on the value of the fatigue crack growth threshold.