The traditional terrain contour matching (TERCOM) algorithm has worse reliability when velocity error or course error is larger. The extend Kalman filtering (EKF) algorithm based BUAA inertial terrain aided navigation (BITAN) algorithm fails to correctly position, leading to a decline of robustness when large initial position error or altimeter noise error occurs. In this paper, we introduce a Robust BUAA inertial terrain aided navigation (RBITAN) algorithm, which is an improved algorithm of BITAN. In the RBITAN algorithm a searching mode approach is designed by the statistic properties of mean absolute difference algorithm, mean square difference algorithm and cross correlation algorithm. The RBITAN gathers the advantages of both the TERCOM algorithm and the BITAN algorithm, and it adopts EKF based BITAN algorithm as the tracking approach. The algorithm is verified by both real digital altitude model and flight-test data. Compared with the BITAN algorithm, the RBITAN algorithm is robust, for it can achieve accurate positioning and tolerate large initial position error or altimeter noise error.