A novel FFT-based phase-field fracture framework for modelling fatigue crack initiation and propagation at the microscale is presented. A damage driving force is defined based on the stored energy and dislocation density, relating phase-field fracture with microstructural fatigue damage. The formulation is numerically implemented using FFT methods to enable modelling of sufficiently large, representative 3D microstructural regions. The early stages of fatigue cracking are simulated, predicting crack paths, growth rates and sensitivity to relevant microstructural features. Crack propagation through crystallographic planes is shown in single crystals, while the analysis of polycrystalline solids reveals transgranular crack initiation and crystallographic crack growth.