For an autonomous underwater vehicle (AUV) underwater localization system based on acoustic two-way travel time measurements, the motion of the AUV during the interrogation-reception time interval, unknown underwater sound velocity, and beacon calibration error affect the performance of the positioning solution. Ignoring these factors significantly deteriorates the performance of the localization system. This paper focuses on the localization problem of AUV in motion with an unknown sound velocity and beacon calibration error. The Cramér–Rao lower bound of the concerned localization problem is first derived as the performance bound of an unbiased estimator. Next, through multi-stage processing, we design a closed-form solution that can attain the corresponding performance bound under small measurement noise conditions. Furthermore, considering that the AUV motion velocity is typically much lower than the sound velocity in practical applications, a simpler and more efficient simplified closed-form solution is proposed, which can guarantee localization performance under the condition that the AUV motion speed is low, as well as small measurement noise. Finally, the theoretical performance and superiority of the proposed solutions were verified through numerical simulation.