The stage error of coordinate measuring machines (CMM) can significantly influence the measurement results, and it places ultra-high requirement on the measurement and calibration tools. A calibration technique based on self-calibration algorithm is presented to calibrate the two-dimensional stage error of CMM, and it can be carried out with a grid plate of the accuracy no higher than test stage. With the proposed self-calibration algorithm based on least squares method, the measurements at various position combinations of rotation and translation are carried out to separate the stage error from measurement results. Both the accuracy and feasibility of the proposed calibration method have been demonstrated by computer simulation and experiments, and the measurement accuracy RMS better than 1μm is achieved. The proposed calibration method has a good anti-noise ability and provides a feasible way to lower the accuracy requirement on standard parts. It is of great practicality for high-accuracy calibration of the stage error of CMM and manufacturing machines in the order of submicron.