Outliers in terrain data are an obstacle to achieving accurate and robust solutions of Underwater Terrain Relative Navigation (UTRN). If not handled properly, navigation may be degraded or even divergent. To address the problem, this paper proposes a terrain-matching algorithm based on the robust estimation theory. In contrast to the conventional approach, the proposed algorithm can significantly reduce the interference of the outliers. Experimental results confirm the good performance of the proposed method.