Efficient navigation is crucial for the reproductive success of many migratory species, often driven by competing pressures to conserve energy and reduce predation risk. Little is known about how non-homing species achieve this balance. We show that sea lamprey (Petromyzon marinus), an ancient extant vertebrate, uses persistent patterns in hydro-geomorphology to quickly and efficiently navigate through complex ecosystems. Hydrodynamic flow models coupled with bathymetric mapping and fine-scale acoustic telemetry revealed movement paths that tracked thalweg scour channels, which are often the deepest and fastest-flowing sections of a river. These paths allow rapid and efficient upstream migration and suggest the existence of a bathymetric highway system. Near-substrate swimming along this path resulted in a median of 5.8% energy savings while also promoting improved safety from nocturnally active predators. We hypothesize sea lampreys use hydrostatic pressure-guided rheotaxis to achieve this navigation. It is likely this tactic relies on sensory information from the animal's primitive lateral line and perhaps the inner ear. Insights from this study can be used to redesign conservation practices to achieve improved control where the animal is invasive and improved fish passage within its native range.