We investigate pure dephasing decoherence (free induction decay and spin echo) of a spin qubit interacting with a nuclear spin bath. While for infinite magnetic field B the only decoherence mechanism is spectral diffusion due to dipolar flip-flops of nuclear spins, with decreasing B the hyperfine-mediated interactions between the nuclear spins become important. We give a theory of decoherence due to these interactions which takes advantage of their long-range nature. For a thermal uncorrelated bath we show that our theory is applicable down to B approximately 10 mT, allowing for comparison with recent experiments in GaAs quantum dots.