In many autonomous underwater vehicle (AUV) applications of long duration, there is a need to accurately determine the AUV's position in an effective way, in terms of both cost and energy consumption. Such situations may occur in reconnaissance operations, mine counter measure operations, and when an AUV is sampling the characteristics of the environment along a track. Since underwater maps are rare, there also is a need for navigational methods that can accommodate very infrequent sampling in terms of time and space. This work describes a new method to solve the above problem by using a multibeam sonar for three-dimensional sampling of the bottom topography and a linear Kalman filter in a nearly optimal way. The proposed method is very accurate, robust, and computationally efficient compared to other methods that are used for terrain navigation. This method is also suitable for continuous navigation.