Location estimation of underwater sensor networks (USNs) has become a critical technology, due to its fundamental role in the sensing, communication and control of ocean volume. However, the asynchronous clock, security attack and mobility characteristics of underwater environment make localization much more challenging as compared with terrestrial sensor networks. This paper is concerned with a privacy-preserving asynchronous localization issue for USNs. Particularly, a hybrid network architecture that includes surface buoys, anchor nodes, active sensor nodes and ordinary sensor nodes is constructed. Then, an asynchronous localization protocol is provided, through which two privacy-preserving localization algorithms are designed to estimate the locations of active and ordinary sensor nodes. It is worth mentioning that, the proposed localization algorithms reveal disguised positions to the network, while they do not adopt any homomorphic encryption technique. More importantly, they can eliminate the effect of asynchronous clock, i.e., clock skew and offset. The performance analyses for the privacy-preserving asynchronous localization algorithms are also presented. Finally, simulation and experiment results reveal that the proposed localization approach can avoid the leakage of position information, while the location accuracy can be significantly enhanced as compared with the other works.