The work is devoted to development of a visual navigation method for an autonomous underwater robot (AUR) using stereo vision. The authors describe the basic principles of implementation of the visual odometry method in accordance with the already established concept of computing, the main stages of which are comparison of the images' features and calculation of the geometric transformation between the neighboring positions of AUR. Two possible modes of operation of a computer program are considered: an on-line mode - the program runs directly on the onboard computer when AUR is moving, and it processes the captured video stream as it becomes available; and a post-processing mode - the program runs on a stationary computer and processes the saved video stream of the whole trajectory. In the first case initially we solve the problem of calculation for each position of the trajectory with the highest possible precision of AUR localization on the current limited sequence of images, and then a problem of provision of real time mode in general. In the second case the task is to ensure a high-precision calculation of AUR localization and increase the speed of calculation through the optimal selection and calculation sequence of the key frames in a path, using the existing video on the entire trajectory. Post-processing is essentially a solution to the task of a full calibration of the sequence of the key frames, which is necessary for solving of the subsequent problem of 3D reconstruction of an underwater scene. A modification of the basic method is suggested. It consists in development and application of an adaptive technique for calculation of AUR trajectory aimed at solving the above problems. It guarantees the desired area of the overlap of the adjacent frames, takes into account the shape of the trajectory and the height of its passage over the sea-floor, driving the dynamic model of AUR, and takes into account the dependence of the number of the actual incoming frames during the movement of the vehicle. Three co-operating techniques realize adaptability: a) selection of the size of the next step, depending on the degree of the overlapping areas of visibility of the stereo camera for two adjacent positions; b) reduction of the step, if the number of the matching features is smaller than the predetermined threshold; and c) cutting off those parts of the image which are not related to the overlap zone of visibility. These techniques provide an optimal way for determination of the sequence of the key frames, in which calculation of the geometric transformation for the local movements is performed. Optimality means achievement of the highest possible accuracy of localization of computation of AUR with the greatest step length in order to ensure the desired overlapping of the adjacent visibility positions. Computation of the local transformation matrixes is carried out proceeding from the condition of the minimal divergences of the points of the two matching 3D clouds. Comparative results of the computational experiments on estimation of the effectiveness of the proposed adaptive method are presented and analyzed. Alternative versions of the individual stages of the general computational scheme are also analyzed. In general, the method can be a useful addition to the traditionally used sonar navigation systems, or a good alternative to them in the conditions of local maneuvering.