Decorrelation is a fundamental computation that optimizes the format of neuronal activity patterns. Channel decorrelation by adaptive mechanisms results in efficient coding, whereas pattern decorrelation facilitates the readout and storage of information. Mechanisms achieving pattern decorrelation, however, remain unclear. We developed a theoretical framework that relates high-dimensional pattern decorrelation to neuronal and circuit properties in a mathematically stringent fashion. For a generic class of random neuronal networks, we proved that pattern decorrelation emerges from neuronal nonlinearities and is amplified by recurrent connectivity. This mechanism does not require adaptation of the network, is enhanced by sparse connectivity, depends on the baseline membrane potential and is robust. Connectivity measurements and computational modeling suggest that this mechanism is involved in pattern decorrelation in the zebrafish olfactory bulb. These results reveal a generic relationship between the structure and function of neuronal circuits that is probably relevant for pattern processing in various brain areas.