In the last few decades, the atomic magnetometry [1–7] has experienced remarkable development and reached to an outstanding sensitivity. This exciting technology is finding applications in various of fields [8–18]. The last two obstacles to further improve the sensitivity of magnetometry are quantum fluctuations and ambient magnetic field. For magnetometry based on optical readout of atomic ensemble’s spin precession, the fundamental limitation of sensitivity is restricted by spin projection noise (SPN) and photon shot noise (PSN). Meanwhile, in practical applications, ambient magnetic field noise which is regarded as a common-mode magnetic-field (CMM) noise is also limiting the sensitivity. Several techniques for reducing PSN [19–25], SPN [26, 27], and CMM noise [7, 28–31] have been proposed, respectively. To achieve the best sensitivity, it is essential to find an efficacious way to eliminate the noises from different sources, simultaneously. For this purpose, here we demonstrate a sub-shot-noise magnetic gradiometer utilizing entangled optical detection with quantum-correlated twin beams. This leads to the simultaneous suppression of PSN and CMM noise. The quantum enhancement spans a frequency range from 7 Hz to 6 MHz with maximum squeezing of 5.5 dB below the standard quantum limit (SQL). The sensitivity of gradient magnetic field reaches 18 fT/cm√Hz at 20 Hz with these sophisticated techniques. Our study opens up new possibilities to use quantum-enhanced technology in developing sensitive magnetometry for practical applications with noisy and physically demanding environments.