The accumulation course angle error of inertial navigation system will decrease the accuracy and reliability of an geomagnetism aided inertial navigation system using a geomagnetic contour matching algorithm. To improve the matching accuracy, the matching track and true track should be as parallel as possible. An improved geomagnetic matching algorithm is presented by introducing rotation angle search technique. To reduce the computation burden, improve operation efficiency and reduce false matching probability, a new search area determination method is proposed, which redefines the search region and reduces the search range. Simulation results demonstrate the effectiveness of the proposed algorithm and the improvement in the matching accuracy.