Bacteria thriving in variable environments rely on chemotaxis for their long-term-survival. Chemotaxis involves the recognition of environmental stimuli through membrane-anchored methyl-accepting chemotaxis proteins (MCPs) and subsequent signal processing by two-component systems. Magnetotactic bacteria (MTB) employ a unique navigation strategy towards preferred micro- or anoxic zones, called magneto-aerotaxis. It comprises passive alignment along the Earth's magnetic field and active flagellar-mediated motility along oxygen gradients. MTB often possess complex chemosensory systems, which are only poorly understood. The genetically tractable Alphaproteobacterium Magnetospirillum gryphiswaldense has an impressive number of ~56 putative genes encoding MCPs; however, MCPs responsible for regulating the aerotactic behavior of M. gryphiswaldense until now had not been identified. Here, we show that a bipartite MCP, consisting of two interacting proteins (a cytoplasmic PAS-domain containing sensory protein (CetB2) and an associated inner membrane-linked transducer protein (CetA2)) functions as a major contributor during bacterial magneto-aerotaxis in M. gryphiswaldense, resulting in an impaired aerotactic response upon deletion of both genes. In addition, three paralogous bipartite systems were identified in M. gryphiswaldense (CetBA1, 3, and 4). Through localization microscopy (3D-SIM) and bacterial two-hybrid analysis, we reveal the organization of paralogous CetBA systems within polar-lateral chemotaxis arrays, and the absence of direct crosstalk between CetA2 and CetB proteins encoded in paralogous bipartite systems. Moreover, employing truncated CetB2 variants, we provide evidence that CetB2 self-interacts via its N-terminal PAS domain, and that CetB2 dimerization is necessary for interaction with CetA2. In conclusion, we provide insights into the molecular control of aerotaxis in MTB. Ultimately, a comprehensive understanding of magneto-aerotaxis might also open the door for future applications in synthetic biology, such as the targeted modification and construction of MTB with altered oxygen preference for microrobotic applications.