Staphylococcus aureus is capable of infecting nearly every organ in the human body. In order to infiltrate and thrive in such diverse host tissues, staphylococci must possess remarkable flexibility in both metabolic and virulence programs. To investigate the genetic requirements for bacterial survival during invasive infection, we performed a transposon sequencing (TnSeq) analysis of S. aureus during experimental osteomyelitis. TnSeq identified 65 genes essential for staphylococcal survival in infected bone and an additional 148 mutants with compromised fitness in vivo. Among the loci essential for in vivo survival was SrrAB, a staphylococcal two-component system previously reported to coordinate hypoxic and nitrosative stress responses in vitro. Healthy bone is intrinsically hypoxic, and intravital oxygen monitoring revealed further decreases in skeletal oxygen concentrations upon S. aureus infection. The fitness of an srrAB mutant during osteomyelitis was significantly increased by depletion of neutrophils, suggesting that neutrophils impose hypoxic and/or nitrosative stresses on invading bacteria. To more globally evaluate staphylococcal responses to changing oxygenation, we examined quorum sensing and virulence factor production in staphylococci grown under aerobic or hypoxic conditions. Hypoxic growth resulted in a profound increase in quorum sensing-dependent toxin production, and a concomitant increase in cytotoxicity toward mammalian cells. Moreover, aerobic growth limited quorum sensing and cytotoxicity in an SrrAB-dependent manner, suggesting a mechanism by which S. aureus modulates quorum sensing and toxin production in response to environmental oxygenation. Collectively, our results demonstrate that bacterial hypoxic responses are key determinants of the staphylococcal-host interaction.