This paper addresses a vision-based terrain referenced navigation of an aircraft. A digital terrain map, in the surroundings of the aircraft, is compared with the camera measurements to estimate the aircraft position. Generally, the measurement equation in the terrain referenced navigation is highly nonlinear due to the sharp changes of terrain. Thus, the conventional extended Kalman filter could lead to unstable navigation solutions. In this paper, a new approach using an adaptive extended Kalman filter is proposed to cope up with the nonlinearity problem. A least squares method is utilized to derive the linearized measurement equations. The Jacobian matrix and sensor noise covariance are modified as a means of smoothing the sharp changes of terrain. Monte Carlo simulations verify that the proposed filter gives the stable navigation solutions, even when there is a large initial error, which is the primary reason for the filter divergence. Moreover, the proposed adaptation barely requires additional computational burden, whereas the high-order filters such as particle filter generally needs higher computational power.