Doppler shift decreases the estimation accuracy of carrier frequency and may result in divergent estimation. It thus degrades the performance of orthogonal frequency division multiplexing (OFDM) underwater acoustic (UWA) communication system. In this paper, the two-step Doppler shift mitigation scheme was adopted to mitigate the Doppler effect. The innovation lied in the second step in which an enhanced carrier frequency offset (CFO) two-time estimation approach on basis of the pilot was proposed to improve the Doppler shift mitigation scheme. In addition, the new Doppler shift mitigation scheme with the proposed approach was implemented in the OFDM communication system under the simulated multipath-spread channel environment. The experiment results show that the new scheme is able to improve the performance of OFDM UWA communication significantly.