In the past few decades, optical magnetometry has experienced remarkable development and reached to an outstanding sensitivity. For magnetometry based on optical readout of atomic ensemble, the fundamental limitation of sensitivity is restricted by spin projection noise and photon shot noise. Meanwhile, in practical applications, ambient magnetic noise also greatly limits the sensitivity. To achieve the best sensitivity, it is essential to find an efficacious way to eliminate the noises from different sources, simultaneously. Here, we demonstrate a quantum magnetic gradiometer with sub-shot-noise sensitivity using entangled twin beams with differential detection. The quantum enhancement spans a frequency range from 7 Hz to 6 MHz with maximum squeezing of 5.5 dB below the quantum noise limit. The sensitivity of gradiometer reaches 18 fT/cm[Formula: see text] at 20 Hz. Our study inspires future possibilities to use quantum-enhanced technology in developing sensitive magnetometry for practical applications in noisy and physically demanding environments.