Legged locomotion on flowing ground (e.g., granular media) is unlike locomotion on hard ground because feet experience both solid- and fluid-like forces during surface penetration. Recent bioinspired legged robots display speed relative to body size on hard ground comparable with high-performing organisms like cockroaches but suffer significant performance loss on flowing materials like sand. In laboratory experiments, we study the performance (speed) of a small (2.3 kg) 6-legged robot, SandBot, as it runs on a bed of granular media (1-mm poppy seeds). For an alternating tripod gait on the granular bed, standard gait control parameters achieve speeds at best 2 orders of magnitude smaller than the 2 body lengths/s (≈60 cm/s) for motion on hard ground. However, empirical adjustment of these control parameters away from the hard ground settings restores good performance, yielding top speeds of 30 cm/s. Robot speed depends sensitively on the packing fraction φ and the limb frequency ω, and a dramatic transition from rotary walking to slow swimming occurs when φ becomes small enough and/or ω large enough. We propose a kinematic model of the rotary walking mode based on generic features of penetration and slip of a curved limb in granular media. The model captures the dependence of robot speed on limb frequency and the transition between walking and swimming modes but highlights the need for a deeper understanding of the physics of granular media.