Abstract: The development of urbanization has made frequent road network changes and road network updating to its current status is of significant importance for automated transportation navigations. Traditional means of surveying and mapping not only takes long time but is also not cost-effective. However, this situation is undergoing significant difference as the location-based services assisted by mobile devices are being implemented, which can collect huge amount of real-time vehicle trajectories composed of geographic locations (trajectory points). Therefore, updating road networks with the vehicle trajectories and using various extracting algorithms attract much focus from both academia and industries. This paper presents a new method of road network updating based on network meshes and vehicle trajectories. Firstly, minimally closed polygons with road segments as the boundaries, referred to road network meshes (RNM) are built by a topology analysis on historical road networks. RNM covers the whole study area and encloses all the trajectory points. Then spatial distance analysis and a Hidden Markov model (HMM) were combined to extract those trajectory points that are from newly developed road within each road network mesh, also termed as mismatched points. Those extracted mismatched points, indicating the locations of the newly built roads, are used to generate point density skeletons from which new roads are thus built. We conclude that the way that the distance analysis coupled with HMM could significantly reduce the time of finding the mismatched trajectory points while keeping high accuracy. Finally, the method is tested by the Portuguese Porto taxi trajectory data, and the experimental results indicate that the incremental road network updated by the proposed model is a promising tool in a massive scale road network synchronization.