Nowadays, with the recent advances of wireless underwater communication and acoustic sensor devices technology, we are witnessing a surge in the exploration and exploitation of the ocean’s abundant natural resources. Accordingly, to fulfill the requirements of the exploration of the ocean, researchers have focused their work toward the design of methods and algorithms for the underwater acoustic sensor networks (UASNs). Although considerable research effort has been devoted to the development of a variety of UASN-based applications, very limited work has addressed the algorithmic design and analysis for UASN. To this end, we propose to provide a comprehensive design, development, and analysis of algorithms and protocols for UASNs. We discuss each of the fundamental UASN building blocks, such as (i) underwater acoustic communication channel modeling, (ii) sustainable coverage and target detection, (iii) Medium Access Control (MAC-layer design and time synchronization, (iv) localization algorithms design, and (v) underwater routing protocol. Then, we illustrate the different protocols from each category and compare their benefits and drawbacks. Finally, we discuss a few potential directions for future research related to the design of future generations of UASNs.