In aircraft navigation the demands on reliability and safety are very high. The importance of accurate position and velocity information becomes crucial when flying an aircraft at low altitudes, and especially during the landing phase. Not only should the navigation system have a consistent description of the position of the aircraft, but also a description of the surrounding terrain, buildings and other objects that are close to the aircraft. Terrain navigation is a navigation scheme that utilizes variations in the terrain height along the aircraft flight path. Integrated with an Inertial Navigation System (INS), it yields high performance position estimates in an autonomous manner, ie without any support information sent to the aircraft. In order to obtain these position estimates, a nonlinear recursive estimation problem must be solved on-line. Traditionally, this filtering problem has been solved by local linearization of the terrain at one or several assumed aircraft positions. Due to changing terrain characteristics, these linearizations will in some cases result in diverging position estimates. In this work, we show how the Bayesian approach gives a comprehensive framework for solving the recursive estimation problem in terrain navigation. Instead of approximating the model of the estimation problem, the analytical solution is approximately implemented. The proposed navigation filter computes a probability mass distribution of the aircraft position and updates this description recursively with each new measurement. The navigation filter is evaluated over a commercial terrain database, yielding accurate position estimates over several types of terrain characteristics. Moreover, in a Monte Carlo analysis, it shows optimal performance as it reaches the Cramér-Rao lower bound.