The incubation and early stages of fatigue crack propagation in polycrystalline metals are often estimated using models based on micromechanics and a definition of the fatigue driving force, such as Fatigue Indicator Parameters or the stored energy density. 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 opens the possibility of tracking how hydrogen embrittlement affects fatigue behaviour at the microstructural level.