Abstract: The Doppler estimation strategy based on the direct search of bit-error rate (BER) produces high computational complexity in orthogonal frequency division multiplexing (OFDM) underwater acoustic communications. To address this issue, a novel Doppler estimation algorithm based on the interval slope of bit-error information is proposed, which replaces the exhaustive grid-wise search of the optimal bit-error information by calculating the interval slope of bit-error information. Moreover, the dynamic variable slope interval is designed according to the Doppler estimation resolution to further accelerate the optimization process, to avoid being trapped at a local minimum as well as to reduce the computational complexity. The numerical simulation and sea trial experiments demonstrate that, compared to the BER search Doppler estimation algorithm, the proposed algorithm achieves almost the same performance with an obviously lower computational cost. Specifically, it yields a BER performance enhancement of not less than 14% compared with the block Doppler estimation, cross-ambiguity function based Doppler estimation and the cross-correlation quasi-gradient Doppler estimation algorithms under the experimental conditions in this paper.