In the spirit of Richardson's original (1948) study of the statistics of deadly conflicts, we study the frequency and severity of terrorist attacks worldwide over the past 38 years, and show that these events are uniformly characterized by the phenomenon of scale invariance, i.e., the frequency scales as an inverse power of the severity, P(x) ~ x^-alpha. We show that this property is a robust feature of terrorism, existing in terrorism that targets both industrialized and non-industrialized countries, across different weapon-types and even over short time-scales. We show that the scaling exponent fluctuates about alpha= 2.5, that the center of the distribution oscillates slightly with a period of roughly tau ~ 13 years, and that current models of event incidence cannot account for the variation in event severity or the scale invariance property of global terrorism. Finally, we propose a simple toy model for the generation of these statistics, and briefly discuss its implications.