The concept of local-scale interactions driving large-scale pattern formation has been supported by numerical simulations, which have demonstrated that simple rules of interaction are capable of reproducing patterns observed in nature. These models of self-organization suggest that characteristic patterns should exist across a broad range of environmental conditions provided that local interactions do indeed dominate the development of community structure. Readily available observations that could be used to support these theoretical expectations, however, have lacked sufficient spatial extent or the necessary diversity of environmental conditions to confirm the model predictions. We use high-resolution satellite imagery to document the prevalence of self-organized vegetation patterns across a regional rainfall gradient in southern Africa, where percent tree cover ranges from 65% to 4%. Through the application of a cellular automata model, we find that the observed power-law distributions of tree canopy cluster sizes can arise from the interacting effects of global-scale resource constraints (that is, water availability) and local-scale facilitation. Positive local feedbacks result in power-law distributions without entailing threshold behaviour commonly associated with criticality. Our observations provide a framework for integrating a diverse suite of previous studies that have addressed either mean wet season rainfall or landscape-scale soil moisture variability as controls on the structural dynamics of arid and semi-arid ecosystems.