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 since 1968. We 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 find that this property is a robust feature of terrorism, persisting when we control for economic development of the target country, the type of weapon used, and even for short time-scales. Further, we show that the center of the distribution oscillates slightly with a period of roughly tau ~ 13 years, that there exist significant temporal correlations in the frequency of severe events, and that current models of event incidence cannot account for these variations or the scale invariance property of global terrorism. Finally, we describe a simple toy model for the generation of these statistics, and briefly discuss its implications.