Cytoskeletal motors act as cargo transporters in cells and may be harnessed for directed transport applications in molecular detection and diagnostic devices. High processivity, the ability to take many steps along a track before dissociating, is often a desirable characteristic because it allows nanoscale motors to transport cargoes over distances on the scale of micrometres, in vivo and in vitro. Natural processive myosins are dimeric and use internal tension to coordinate the detachment cycles of the two heads. Here, we show that processivity can be enhanced in engineered myosins using two non-natural strategies designed to optimize the effectiveness of random, uncoordinated stepping: (1) the formation of three-headed and four-headed myosins and (2) the introduction of flexible elements between heads. We quantify improvements using systematic single-molecule characterization of a panel of engineered motors. To test the modularity of our approach, we design a controllably bidirectional myosin that is robustly processive in both forward and backward directions, and also produce the fastest processive cytoskeletal motor measured so far, reaching a speed of 10 µm s(-1).