In this paper, an underwater navigation system with adaptive receding horizon Kalman filter (ARHKF) is studied. It is well known that incorrect statistical information and temporal disturbance invoke errors of any navigation systems with Kalman filter, which makes the autonomous navigation difficult in real underwater environment. In this context, two kinds of problems are herein considered. The first one is the development of an algorithm, which estimates the noise covariance of a linear discrete time-varying stochastic system. The second one is the implementation of ARHKF to underwater navigation systems. The performance of the derived estimation algorithm of noise covariance and the ARHKF are verified by simulation and experiment in the towing tank of Seoul National University.