Abstract Autonomous underwater vehicle (AUV) networks are used for coordinated missions such as area mapping and remote surveillance. AUVs are typically deployed by a central platform such as a ship or a submarine, and they operate in an unattended environment. Although there is no need for continuous monitoring of AUV nodes, the central platform may occasionally need to send messages, route updates, or mission commands to the AUV fleet. Nodes in an AUV network are mobile and self-powered. Moreover, periodic exchange of neighborhood messages is not practical due to large propagation delays. Therefore, reliable, low-latency, and energy-efficient solutions are needed to meet the performance requirements of ad hoc AUV networks. We propose P-AUV as a routing and medium access protocol, which depends on location estimation at each node. Data required for packet relaying decision is carried in the header of each data packet. Loop-free routes are generated, where relay candidates closer to the sink nodes are prioritized. In order to control medium access and to avoid collisions, each node selects a backoff interval according to its own position. We analyze the performance of our solution and we compare P-AUV with probabilistic broadcast in terms of several network parameters. Our results indicate that P-AUV improves packet delivery ratio and end-to-end delay along with lifetime of AUV networks.