Dimeric myosin VI moves processively hand-over-hand along actin filaments. We have characterized the mechanism of this processive motion by measuring the impact of structural and chemical perturbations on single-molecule processivity. Processivity is maintained despite major alterations in lever arm structure, including replacement of light chain binding regions and elimination of the medial tail. We present kinetic models that can explain the ATP concentration-dependent processivities of myosin VI constructs containing either native or artificial lever arms. We conclude that detailed tuning of structure and intramolecular communication are dispensable for processive motion, and further show theoretically that one proposed type of nucleotide gating can be detrimental rather than beneficial for myosin processivity.