The grain size distribution of deformed rocks may provide valuable information about their deformation history and the associated mechanisms. Here we present a unique set of olivine grain size distributions from ultramafic rocks deformed under a wide range of stress and strain rate conditions. Both experimentally deformed and naturally deformed samples are included. We observe a surprisingly uniform behavior, and most samples show power law grain size distributions. Convincing lognormal distributions across all scales were only observed for samples experimentally deformed at high temperature (1200 °C) and for some mantle-deformed natural samples. Single power law distributions were observed for natural samples deformed by brittle mechanisms and by samples deformed experimentally in the regime of low-temperature plasticity. Most natural samples show a crossover in power law scaling behavior near the median grain size from a steep slope for the larger grain fraction to a more gentle slope for the smaller grains. The small grain fraction shows a good data collapse when normalized to the crossover length scale. The associated power law slope indicates a common grain size controlling process. We propose a model that explains how such a scaling behavior may arise in the dislocation creep regime from the competition between the rate involved in the dislocation dynamics and the imposed strain rate. The common departure from lognormal distributions suggests that naturally deformed samples often have a deformation history that is far from a steady state scenario and probably reflects deformation under highly variable stress and strain rates.