In this paper, a robust correction algorithm for Dead Reckoning (DR) navigation system is proposed based on digital map. The DR system here contains an IMU unit, in which 3 Ring Laser Gyros (RLG) and 3 accelerometers are consisted, providing azimuth angle, and an odometer that can provide mileage increament. An improved Map-Match algorithm is designed and implemented, which composes a “road correction” unit and a “road projection” unit based on geometry theory. To enhance the robustness of the system, a new communication protocol is designed. Based on the information provided by digital map, the DR system can not only corrects the position output, but also estimates the odometer scale factor error with a newly designed online calibration algorithm. Road test is conducted and the results have testified the effectiveness of the algorithm.