Inertial navigation system (INS) is not susceptible to external interference and are currently the most widely used localization method for military vehicles. However, INS relies on dead reckoning for localization, which accumulates errors during the integral and recursive solving process. In order to suppress the INS drift under long voyage, we propose a map-matching algorithm based on Hidden Markov Model (HMM) for INS data, which adopts R-Tree to store the priori map, detects the vehicle trajectory features in real time by sliding window and matches them with the priori map, and corrects the INS localization data by weighted translation vector. After the test, the algorithm can maintain stability under different road sections and vehicle speeds, and the average positioning error is reduced from 39.31 m to 16.14 m under long runtime, which comply with the requirements of military vehicle localization.