In this paper, the interference with magnetic heading estimation caused by a local near-surface magnetic anomaly is studied and an error compensation method based on discrete cosine transform (DCT) is proposed. Firstly, the magnetic gradient signals of the magnetic anomaly source are calculated from the measured vector sum of the anomalous magnetic field and the background geomagnetic field. Then the magnetic vector signals generated by the near-surface magnetic anomaly sources are calculated by the time-domain differential theorem of DCT. Finally, the background geomagnetic field vector is obtained and compensation for the magnetic heading perturbation is achieved. Numerical simulations show that the proposed method can accurately compensate for the magnetic heading perturbation caused by near-surface magnetic anomaly sources, and experimental results reveal the reliability and practicability of the proposed method.