We present a gradient-based theoretical framework for predicting hydrogen assisted fracture in elastic-plastic solids. The novelty of the model lies in the combination of: (i) stress-assisted diffusion of solute species, (ii) strain gradient plasticity, and (iii) a hydrogen-sensitive phase field fracture formulation, inspired by first principles calculations. The theoretical model is numerically implemented using a mixed finite element formulation and several boundary value problems are addressed to gain physical insight and showcase model predictions. The results reveal the critical role of plastic strain gradients in rationalising decohesion-based arguments and capturing the transition to brittle fracture observed in hydrogen-rich environments. Large crack tip stresses are predicted, which in turn raise the hydrogen concentration and reduce the fracture energy. The computation of the steady state fracture toughness as a function of the cohesive strength shows that cleavage fracture can be predicted in otherwise ductile metals using sensible values for the material parameters and the hydrogen concentration. In addition, we compute crack growth resistance curves in a wide variety of scenarios and demonstrate that the model can appropriately capture the sensitivity to: the plastic length scales, the fracture length scale, the loading rate and the hydrogen concentration. Model predictions are also compared with fracture experiments on a modern ultra-high strength steel, AerMet100. A promising agreement is observed with experimental measurements of threshold stress intensity factor $Kth$ over a wide range of applied potentials.