Body size greatly affects how organisms interact with their environments. However, the macroevolutionary patterns of body size across many major metazoan clades and their constraining mechanisms remain elusive. A new high-resolution body size dataset covering 2435 species from 1091 genera of Cambrian and Ordovician trilobites reveals that body size evolution changes episodically, with three marked reductions in size. Such a pattern rules out a persistent Cope's rule dynamic. Rather, we find a strong temporal link between body size changes and major fluctuations in marine redox, supporting the hypothesis that marine oxygen levels exerted a primary control on the tempo and mode of trilobite body size evolution. These further imply a dominant role for marine oxygen in early animal evolution.