A newly deployed underwater acoustic network is considered in which the nodes have no knowledge of their neighbors’ IDs and locations. Normal network functions such as routing typically rely on the availability of this information so node discovery is the first step in building the network. It is also crucial for network recovery upon failure or loss of a node. We propose a protocol for network discovery whose goal is to establish full connectivity in a time-efficient manner, at minimum energy expenditure, and with no global synchronization. The proposed protocol operates in cycles, each led by a single node called the cycle leader. The leader sends out a discovery packet, to which all the nodes within range reply in a random access fashion. Power control is implemented using several discrete levels, ensuring that a node uses only the minimum level needed for a new discovery. We consider both an ideal situation with time-invariant propagation conditions, and a more realistic situation with fading. The protocol performance is evaluated in terms of the time and energy it takes to complete, and compared to the reference case of broadcast discovery. Simulation results show that substantial energy savings are available from distributed power control, while the completion time stays well within acceptable limits. More importantly, it is shown that simple adjustments to the protocol can overcome the otherwise deleterious effects of fading.