Rising temperatures are associated with reduced body size in many marine species, but the biological cause and generality of the phenomenon is debated. We derive a predictive model for body size responses to temperature and oxygen (O) changes based on thermal and geometric constraints on organismal O supply and demand across the size spectrum. The model reproduces three key aspects of the observed patterns of intergenerational size reductions measured in laboratory warming experiments of diverse aquatic ectotherms (i.e., the "temperature-size rule" [TSR]). First, the interspecific mean and variability of the TSR is predicted from species' temperature sensitivities of hypoxia tolerance, whose nonlinearity with temperature also explains the second TSR pattern-its amplification as temperatures rise. Third, as body size increases across the tree of life, the impact of growth on O demand declines while its benefit to O supply rises, decreasing the size dependence of hypoxia tolerance and requiring larger animals to contract by a larger fraction to compensate for a thermally driven rise in metabolism. Together our results support O limitation as the mechanism underlying the TSR, and they provide a physiological basis for projecting ectotherm body size responses to climate change from microbes to macrofauna. For small species unable to rapidly migrate or evolve greater hypoxia tolerance, ocean warming and O loss in this century are projected to induce >20% reductions in body mass. Size reductions at higher trophic levels could be even stronger and more variable, compounding the direct impact of human harvesting on size-structured ocean food webs.