We establish a new mechanism for self-propelled motion of droplets, in which ordering of the nanoscale step morphology by sublimation beneath the droplets themselves acts to drive them perpendicular and up the surface steps. The mechanism is demonstrated and explored for Ga droplets on GaP(111)B, using several experimental techniques allowing studies of the structure and dynamics from micrometers to the atomic scale. We argue that the simple assumptions underlying the propulsion mechanism make it relevant for a wide variety of materials systems.