Molecular motors employ chemical energy to generate unidirectional mechanical output against a track while navigating a chaotic cellular environment, potential disorder on the track, and against Brownian motion. Nevertheless, decades of nanometer-precise optical studies suggest that myosin-5a, one of the prototypical molecular motors, takes uniform steps spanning 13 subunits (36 nm) along its F-actin track. Here, we use high-resolution interferometric scattering microscopy to reveal that myosin takes strides spanning 22 to 34 actin subunits, despite walking straight along the helical actin filament. We show that cumulative angular disorder in F-actin accounts for the observed proportion of each stride length, akin to crossing a river on variably spaced stepping stones. Electron microscopy revealed the structure of the stepping molecule. Our results indicate that both motor and track are soft materials that can adapt to function in complex cellular conditions.