This work explores the consequences of strain crystallization on rubber's fatigue crack nucleation behavior over an extensive space of operating conditions, including tension and compression loading states, and relaxing and non-relaxing cycles. The study considers, via computation, how the nonlinear elastic stress-strain behavior, the fatigue crack growth characteristics, and the damage accumulation law combine to produce the Haigh diagram and the Cadwell diagram. Four hypothetical materials are studied, which differ in their crystallization and associated fatigue crack growth behavior. The calculations demonstrate that a relatively simple idealization can credibly predict the unique shape and sensitivities of observed fatigue behavior over a wide range of conditions. They also clarify how features of the Haigh and Cadwell diagrams are linked to the occurrence of crystallization and to parameters such as the power-law slope and the fatigue threshold.