AROTAN provides for autonomous terrain aided navigation that is fully independent of the position uncertainty of the vehicle during flight. AROTAN aligns a grid to the search space and periodically updates the search space during the measurement history to account for growth in position uncertainty. AROTAN computes terrain sufficiency statistics for a moving history to provide robust criteria for when to perform the correlation. A post-correlation refinement provides an additional correction of the horizontal position error and a correction of the altitude. AROTAN can quickly provide the vehicle's location based on the correlation from a single measurement history.