The accuracy of magnetic heading sensor is reduced by the impact of manufacturing technology and local magnetic interferences. The singularity of constraint matrix in traditional calibration algorithm leads to unstable results. Therefore, an improved least-square ellipsoid fitting method is proposed in this paper. The error source and the deviation mathematical model are introduced. On the basis of the analysis on singularity of the constraints matrix, parameter extraction by the improved least-square ellipsoid fitting method is given. The new method successfully overcomes the instability of the traditional algorithm, and reduces the computation load. Simulation and experimental results show that this method is effective in calibrating magnetic heading sensor. The heading precision of the sensor acquired after calibration is better than 0.42º.