For the purpose of reducing the cost, size, and weight of the integrated navigation system of an AUV (autonomous underwater vehicle), and improving the stealth of this system, an integrated navigation algorithm based on a propeller tachometer is proposed. The algorithm consists of five steps: ① establishing the resistance model of AUV, ② establishing the thrust model, ③ utilizing the measured speeds obtained from the AUV’s voyage trials for calibration, ④ discrimination and replacement of outliers from the tachometer measurements, and ⑤ establishing a linear Kalman filter (LKF) with water currents as state variables. This paper provides the modeling procedure, formula derivations, model parameters, and algorithm process, etc. Through research and analysis, the proposed algorithm’s accuracy has been improved. The specific values of the localization error are detailed in the main text. Therefore, the proposed algorithm has high accuracy, a strong anti-interference capability, and good robustness. Moreover, it exhibits certain adaptability to complex environments and value for practical engineering.