In the absence of salient sensory cues to guide behavior, animals must still execute sequences of motor actions in order to forage and explore. How such successive motor actions are coordinated to form global locomotion trajectories is unknown. We mapped the structure of larval zebrafish swim trajectories in homogeneous environments and found that trajectories were characterized by alternating sequences of repeated turns to the left and to the right. Using whole-brain light-sheet imaging, we identified activity relating to the behavior in specific neural populations that we termed the anterior rhombencephalic turning region (ARTR). ARTR perturbations biased swim direction and reduced the dependence of turn direction on turn history, indicating that the ARTR is part of a network generating the temporal correlations in turn direction. We also find suggestive evidence for ARTR mutual inhibition and ARTR projections to premotor neurons. Finally, simulations suggest the observed turn sequences may underlie efficient exploration of local environments.