The incubation and early stages of fatigue crack propagation in polycrystalline metals are typically estimated using models based on micromechanics and a definition of the fatigue driving force, such as Fatigue Indicator Parameters or the stored energy density concept. Recently, phase-field models have demonstrated a strong ability to solve fracture problems that involve plasticity or fatigue. Although these techniques are powerful, they are computationally expensive. However, the bottleneck of these approaches can be overcome by using Fast Fourier Transform (FFT) based methods, which exhibit remarkable numerical performance compared to finite element methods. In this work, a new FFT-based phase-field fatigue framework is proposed by relating the phase-field fracture to fatigue driving force definitions within the context of crystal plasticity. The coupling of plasticity and fatigue damage reveals the interaction between the two, which allows capturing the competition between transgranular and intergranular fatigue crack propagation mechanisms. The early stages of fatigue cracking in polycrystals are simulated, demonstrating sensitivity to microstructural features. The use of FFT solvers enables the simulation of large 3D microstructural regions to predict lifetimes during the early stages of fatigue. This computational approach has been extended to consider environmental factors, such as corrosion or hydrogen attack, in addition to fatigue behavior at the microstructural level. The extension of this computational approach allows considering environmental factors, such as corrosion or hydrogen embrittlement, in combination with fatigue behavior at the microstructural level.