We present a new theoretical and numerical phase field-based formulation for predicting hydrogen-assisted fatigue. The coupled deformation-diffusion-damage model presented enables predicting fatigue crack nucleation and growth for arbitrary loading patterns and specimen geometries. The role of hydrogen in increasing fatigue crack growth rates and decreasing the number of cycles to failure is investigated. Our numerical experiments enable mapping the three loading frequency regimes and naturally recover Paris law behaviour for various hydrogen concentrations. In addition, Virtual S-N curves are obtained for both notched and smooth samples, exhibiting a good agreement with experiments.