The sensation of gravity anchors our perception of the environment and is crucial for navigation. However, the neural circuits that transform gravity into commands for navigation are undefined. We first determined that larval zebrafish (Danio rerio) navigate vertically by maintaining a consistent heading across a series of upward climb or downward dive bouts. Gravity-blind mutant fish swim with more variable heading and excessive veering, leading to inefficient vertical navigation. After targeted photoablation of ascending vestibular neurons and spinal projecting midbrain neurons, but not vestibulospinal neurons, vertical navigation was impaired. These data define a sensorimotor circuit that uses evolutionarily-conserved brainstem architecture to transform gravitational signals into persistent heading for vertical navigation. The work lays a foundation to understand how vestibular inputs allow animals to move efficiently through their environment.