The spreading of evolutionary novelties across populations is the central element of adaptation. Unless populations are well mixed (like bacteria in a shaken test tube), the spreading dynamics depend not only on fitness differences but also on the dispersal behavior of the species. Spreading at a constant speed is generally predicted when dispersal is sufficiently short ranged, specifically when the dispersal kernel falls off exponentially or faster. However, the case of long-range dispersal is unresolved: Although it is clear that even rare long-range jumps can lead to a drastic speedup--as air-traffic-mediated epidemics show--it has been difficult to quantify the ensuing stochastic dynamical process. However, such knowledge is indispensable for a predictive understanding of many spreading processes in natural populations. We present a simple iterative scaling approximation supported by simulations and rigorous bounds that accurately predicts evolutionary spread, which is determined by a trade-off between frequency and potential effectiveness of long-distance jumps. In contrast to the exponential laws predicted by deterministic "mean-field" approximations, we show that the asymptotic spatial growth is according to either a power law or a stretched exponential, depending on the tails of the dispersal kernel. More importantly, we provide a full time-dependent description of the convergence to the asymptotic behavior, which can be anomalously slow and is relevant even for long times. Our results also apply to spreading dynamics on networks with a spectrum of long-range links under certain conditions on the probabilities of long-distance travel: These are relevant for the spread of epidemics.