Most motile bacteria navigate within gradients of external chemical stimuli by regulating the length of randomly oriented swimming episodes. Magnetotactic bacteria are characterized by chains of intracellular ferromagnetic nanoparticles and their ability to sense the geomagnetic field, which is believed to facilitate directed motion, but is not well understood at the behavioural and molecular level. Here, we show that cells of Magnetospirillum gryphiswaldense unexpectedly display swimming polarity that depends on aerotactic signal transduction through one of its four chemotaxis operons (cheOp1). Growth of cells in magnetic fields superimposed on oxygen gradients results in a gradual inherited bias of swimming runs with one of the cell poles leading, such that the resulting overall swimming direction of entire populations can be reversed by changes in oxygen concentration. These findings clearly show that there is a direct molecular link between aerotactic sensing and the determination of magnetotactic polarity, through the sensory pathway, CheOp1.