Homeostatic sensory systems detect small deviations in temperature, water balance, pH, and energy needs to regulate adaptive behavior and physiology. In C. elegans, a homeostatic preference for intermediate oxygen (O2) levels requires cGMP signaling through soluble guanylate cyclases (sGCs), proteins that bind gases through an associated heme group. Here we use behavioral analysis, functional imaging, and genetics to show that reciprocal changes in O2 levels are encoded by sensory neurons that express alternative sets of sGCs. URX sensory neurons are activated by increases in O2 levels, and require the sGCs gcy-35 and gcy-36. BAG sensory neurons are activated by decreases in O2 levels, and require the sGCs gcy-31 and gcy-33. The sGCs are instructive O2 sensors, as forced expression of URX sGC genes causes BAG neurons to detect O2 increases. Both sGC expression and cell-intrinsic dynamics contribute to the differential roles of URX and BAG in O2-dependent behaviors.