The unique properties of nonlinear waves have been recently exploited to enable a wide range of applications, including impact mitigation, asymmetric transmission, switching, and focusing. Here, we demonstrate that the propagation of nonlinear waves can be as well harnessed to make flexible structures crawl. By combining experimental and theoretical methods, we show that such pulse-driven locomotion reaches a maximum efficiency when the initiated pulses are solitons and that our simple machine can move on a wide range of surfaces and even steer. Our study expands the range of possible applications of nonlinear waves and demonstrates that they offer a new platform to make flexible machines to move.