A modified adaptive Kalman filter (AKF) algorithm is proposed to make underwater multi-target tracking with uncertain measurement noise reliable. By utilizing the proposed AKF algorithm with three core points, including an adaptive fading factor, measurement noise covariance adjustment, and an adaptive weighting factor, the unknown measurement noise and state vector can be estimated with good accuracy and robustness. The practical trial data verify this algorithm, and it has proven superior to all traditional algorithms in this Letter based on the results that it reduces the estimated position RMSEs by at least 10.29% while estimated velocity RMSEs by at least 52.57%.