Abstract: Map matching can improve the positioning precision in Vehicle Navigation Positioning System. Present algorithms take into account only a certain influencing factor. A new algorithm relying on history tracking is presented. It traces all possible sources of errors and makes corrections accordingly throughout the whole process of data processing, including checking the validity of GPS readings, verifying whether the previous matching is a branching point, is it located within the tolerance of shortest range or still following the previous road etc. Experiments show that the synthesized approach is effective and reliable.