The velocity field of dark matter and galaxies reflects the continued action of gravity throughout cosmic history. We show that the low-order moments of the pairwise velocity distribution v_{12} are a powerful diagnostic of the laws of gravity on cosmological scales. In particular, the projected line-of-sight galaxy pairwise velocity dispersion σ_{12}(r) is very sensitive to the presence of modified gravity. Using a set of high-resolution N-body simulations, we compute the pairwise velocity distribution and its projected line-of-sight dispersion for a class of modified gravity theories: the chameleon f(R) gravity and Galileon gravity (cubic and quartic). The velocities of dark matter halos with a wide range of masses would exhibit deviations from general relativity at the (5-10)σ level. We examine strategies for detecting these deviations in galaxy redshift and peculiar velocity surveys. If detected, this signature would be a "smoking gun" for modified gravity.