Terramechanics has advanced the mobility of off-road vehicles on deformable ground like sand and soil. However, because of approximations specific to large wheels and tracks with small sinkage relative to wheel/track size, terramechanical models often over-predict speeds for small vehicles with relatively large sinkage (e.g. Mars rovers), and do not apply to legged locomotors whose leg-ground interaction can be even more complex. Here we develop the first general model for predicting legged locomotion on granular media (e.g. sand) [Li el al, Science, 339, 1408-1412 (2013)]. We measure the lift and drag forces on a small plate element moving in granular media as a function of its depth, orientation, and movement direction. Both lift and drag forces on the plate element are proportional to its depth, but depend sensitively on its orientation and movement direction. Without any fitting parameters, summation of element forces over the intruder’s leading surface accurately predicts the net lift and drag forces on legs of complex geometry and kinematics moving in granular media. Using the resistive force model, a multi-body dynamic simulation accurately predicts the speed of a small (13 cm, 150 g) legged robot on granular media using a variety of leg shapes and a large range of stride frequencies. Furthermore, we discover that the complex dependence of lift and drag on intruder depth, orientation, and movement direction is generic to a large variety of granular media (including natural sands) varying in particle size, shape, density, friction, polydispersity, and compaction. Inspired by this generality, we develop a practical procedure to allow application of our model in the field by a single penetrometer measurement. Our resistive force model may not be limited to predicting legged locomotion; we hypothesize that the linear superposition of element forces can apply to devices of other geometry and kinematics (e.g. wheels, tracks, earth movers).