We investigate the influence of microstructural traps in hydrogen-assisted fatigue crack growth. To this end, a new formulation combining multi-trap stress-assisted diffusion, mechanism-based strain gradient plasticity and a hydrogen- and fatigue-dependent cohesive zone model is presented and numerically implemented. The results show that the ratio of loading frequency to effective diffusivity governs fatigue crack growth behaviour. Increasing the density of \emph{beneficial} traps, not involved in the fracture process, results in lower fatigue crack growth rates. The combinations of loading frequency and carbide trap densities that minimise embrittlement susceptibility are identified, providing the foundation for a rational design of hydrogen-resistant alloys.