Specialized oxygen-sensing cells in the nervous system generate rapid behavioural responses to oxygen. We show here that the nematode Caenorhabditis elegans exhibits a strong behavioural preference for 5-12% oxygen, avoiding higher and lower oxygen levels. 3',5'-cyclic guanosine monophosphate (cGMP) is a common second messenger in sensory transduction and is implicated in oxygen sensation. Avoidance of high oxygen levels by C. elegans requires the sensory cGMP-gated channel tax-2/tax-4 and a specific soluble guanylate cyclase homologue, gcy-35. The GCY-35 haem domain binds molecular oxygen, unlike the haem domains of classical nitric-oxide-regulated guanylate cyclases. GCY-35 and TAX-4 mediate oxygen sensation in four sensory neurons that control a naturally polymorphic social feeding behaviour in C. elegans. Social feeding and related behaviours occur only when oxygen exceeds C. elegans' preferred level, and require gcy-35 activity. Our results suggest that GCY-35 is regulated by molecular oxygen, and that social feeding can be a behavioural strategy for responding to hyperoxic environments.