High end-to-end delay is a significant challenge in the data collection process in the underwater environment. Autonomous Underwater Vehicles (AUVs) are a considerably reliable source of data collection if they have significant trajectory movement. Therefore, in this paper, a new routing algorithm known as Elliptical Shaped Efficient Data Gathering (ESEDG) is introduced for the AUV movement. ESEDG is divided into two phases: first, an elliptical trajectory has been designed for the horizontal movement of the AUV. In the second phase, the AUV gathers data from Gateway Nodes (GNs) which are associated with Member Nodes (MNs). For their association, an end-to-end delay model is also presented in ESEDG. The hierarchy of data collection is as follows: MNs send data to GNs, the AUV receives data from GNs, and forwards it to the sink node. Furthermore, the ESEDG was evaluated on the network simulator NS-3 version 3.35, and the results were compared to existing data collection routing protocols DSG–DGA, AEEDCO, AEEDCO-A, ALP, SEDG, and AEDG. In terms of network throughput, end-to-end delay, lifetime, path loss, and energy consumption, the results showed that ESEDG outperformed the baseline routing protocols.