Terrain matching algorithms use terrain features to aid navigation. To improve navigation accuracy of the terrain matching algorithm, this study proposes a terrain matching algorithm based on the morphological enhanced histogram of oriented gradients (EHOG). The proposed algorithm performs morphological closed operations to preprocess the real-time elevation map (REM) obtained by the interferometric synthetic aperture radar (InSAR), thereby obtaining the EHOG features. Then, it converts the terrain matching into the matching of the HOG feature descriptors. Euclidean distance between eigenvectors is used as a measure of similarity. In the matching process, we have adopted a three-step optimization matching search strategy that combines rough matching, smaller matching, and fine matching to improve the algorithm's real-time performance. Experimental results show that, compared to the unenhanced HOG algorithm and the traditional gradient cross-correlation algorithm, the proposed algorithm has better matching accuracy and noise resistance. Simultaneously, it has shown strong robustness and practicality and is well suited for InSAR terrain matching.