Polymorphonuclear neutrophils (PMNs) are increasingly recognized to influence solid tumor development, but why their effects are so context dependent and even frequently divergent remains poorly understood. Using an autochthonous mouse model of uterine cancer and the administration of respiratory hyperoxia as a means to improve tumor oxygenation, we provide in vivo evidence that hypoxia is a potent determinant of tumor-associated PMN phenotypes and direct PMN-tumor cell interactions. Upon relief of tumor hypoxia, PMNs were recruited less intensely to the tumor-bearing uterus, but the recruited cells much more effectively killed tumor cells, an activity our data moreover suggested was mediated via their production of NADPH oxidase-derived reactive oxygen species and MMP-9. Simultaneously, their ability to promote tumor cell proliferation, which appeared to be mediated via their production of neutrophil elastase, was rendered less effective. Relieving tumor hypoxia thus greatly improved net PMN-dependent tumor control, leading to a massive reduction in tumor burden. Remarkably, this outcome was T cell independent. Together, these findings identify key hypoxia-regulated molecular mechanisms through which PMNs directly induce tumor cell death and proliferation in vivo and suggest that the contrasting properties of PMNs in different tumor settings may in part reflect the effects of hypoxia on direct PMN-tumor cell interactions.